A tight analysis of the greedy algorithm for set cover
Explore this paper's citation graph
Summary
The first substantial improvement of the 20-year-old classical harmonic upper bound,H(m), of Johnson, Lovasz, and Chvatal, is provided and the approximation guarantee for the greedy algorithm is better than the guarantee recently established by Srinivasan for the randomized rounding technique, thus improving the bounds on theintegrality gap.
- Type
- article
- Published
- 1996-07-01
- Cited by
- 464
- References
- 14
- Access
- Open access
- OpenAlex
- https://openalex.org/W1969665089
- Semantic Scholar
- https://api.semanticscholar.org/CorpusID:758709
Keywords
Cover (algebra), Citation, Computer science, Greedy algorithm, State (computer science)
References
- Approximating set cover via local improvements
- Approximating discrete collections via local improvements
- A threshold of ln n for approximating set cover (preliminary version)
- Computers and Intractability: A Guide to the Theory of NP-Completeness
- Approximation algorithms for combinatorial problems
- On the hardness of approximating minimization problems
- Improved approximations of packing and covering problems
- A Greedy Heuristic for the Set-Covering Problem
- On the ratio of optimal integral and fractional covers
- A threshold of ln n for approximating set cover
- Approximation on the Web: A Compendium of NP Optimization Problems
- Reducibility Among Combinatorial Problems
- A compendium of NP optimization problems
Cited by
- A Note on Set Cover Inapproximability Independent of Universe Size
- Heuristic algorithms for wireless mesh network planning
- Обобщенные покрытия и их аппроксимации
- Approximation for Dominating Set Problem with Measure Functions
- Accelerating Protein Sequence Alignment with Different Parallel Hardware Platforms
- RFID Antenna Coverage Optimization
- A fuzzy theory based evolutionary approach for driver scheduling
- Combinatorial Problems of Packing and Covering and Related Problems of Integer Linear Programming
- Probabilistic analysis of the greedy algorithm
- Identifying Codes and the Set Cover Problem
- Approximation algorithms for set cover and related problems
- Survey of Approximation Algorithms for Set Cover Problem
- When Does Greedy Learning of Relevant Features Succeed? --- A Fourier-based Characterization ---
- Active learning of interaction networks
- The Greedy Algorithm and its Application to the Construction of a Continuous Speech Database
- Analyse d'Algorithme
- A probabilistic alternative to regression suites
- Position-based routing algorithms for three-dimensional ad hoc networks
- Many objective optimization and hypervolume based search
- Behavior-Aware Design, Optimization and Information Mining in Wearable Sensing Systems
Related papers
- ФОРМИРОВAНИЕ ГОТОВНОСТИ БУДУЩИХ ПЕДAГОГОВ К ОРГAНИЗAЦИИ РAБОТЫ ПО РAЗВИТИЮ ВAЛЕОЛОГИЧЕСКОЙ КУЛЬТУРЫ ШКОЛЬНИКОВ
- चितलवाना पंचायत समिति में मानव गरीबी सूचकांक - 2016 ( à¤à¤• गà¥à¤°à¤¾à¤® सà¥à¤¤à¤°à¥€à¤¯ à¤à¥Œà¤—ोलिक अधà¥à¤¯à¤¯à¤¨ )
- A GEOMETRIC MEAN IN THE FURUTA INEQUALITY
- Remarks on Algorithm 2, Algorithm 3, Algorithm 15, Algorithm 25 and Algorithm 26