Rounding algorithms for covering problems
- 1 January 1998
- journal article
- Published by Springer Nature in Mathematical Programming
- Vol. 80 (1) , 63-89
- https://doi.org/10.1007/bf01582131
Abstract
No abstract availableKeywords
This publication has 19 references indexed in Scilit:
- Approximation algorithms for combinatorial problemsPublished by Elsevier ,2007
- Almost optimal set covers in finite VC-dimensionPublished by Association for Computing Machinery (ACM) ,1994
- A primal-dual approximation algorithm for generalized Steiner network problemsPublished by Association for Computing Machinery (ACM) ,1993
- Randomized rounding: A technique for provably good algorithms and algorithmic proofsCombinatorica, 1987
- A fast approximation algorithm for the multicovering problemDiscrete Applied Mathematics, 1986
- A Sharp Bound on the Ratio Between Optimal Integer and Fractional CoversMathematics of Operations Research, 1984
- Approximation Algorithms for the Set Covering and Vertex Cover ProblemsSIAM Journal on Computing, 1982
- A linear-time approximation algorithm for the weighted vertex cover problemJournal of Algorithms, 1981
- A Greedy Heuristic for the Set-Covering ProblemMathematics of Operations Research, 1979
- On the ratio of optimal integral and fractional coversDiscrete Mathematics, 1975