Tight Approximation Bounds for Greedy Frugal Coverage Algorithms

DOI10.1007/978-3-642-21204-8_22zbMath1329.90116OpenAlexW25604785MaRDI QIDQ3004668

Christos Kaklamanis, Maria Kyropoulou, Ioannis Caragiannis

Publication date: 3 June 2011

Published in: Frontiers in Algorithmics and Algorithmic Aspects in Information and Management (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-21204-8_22

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Unnamed Item
• Uniform unweighted set cover: the power of non-oblivious local search
• Analysis of approximation algorithms for \(k\)-set cover using factor-revealing linear programs
• Approximation algorithms for combinatorial problems
• Oblivious algorithms for the maximum directed cut problem
• Donation Center Location Problem
• A threshold of ln n for approximating set cover
• An Improved Approximation Bound for Spanning Star Forest and Color Saving
• Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
• Approximating the Unweighted ${k}$-Set Cover Problem: Greedy Meets Local Search
• Wavelength Management in WDM Rings to Maximize the Number of Connections

This page was built for publication: Tight Approximation Bounds for Greedy Frugal Coverage Algorithms