An Improved Approximation Algorithm for Vertex Cover with Hard Capacities
- 18 June 2003
- book chapter
- Published by Springer Nature
- p. 164-175
- https://doi.org/10.1007/3-540-45061-0_15
Abstract
No abstract availableKeywords
This publication has 12 references indexed in Scilit:
- Approximation algorithms for combinatorial problemsPublished by Elsevier ,2007
- Covering problems with hard capacitiesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Dependent rounding in bipartite graphsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Generalized submodular cover problems and applicationsTheoretical Computer Science, 2001
- Tight approximation results for general covering integer programsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2001
- Heuristics for the fixed cost median problemMathematical Programming, 1982
- Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative DataMathematics of Operations Research, 1982
- Approximation Algorithms for the Set Covering and Vertex Cover ProblemsSIAM Journal on Computing, 1982
- A Greedy Heuristic for the Set-Covering ProblemMathematics of Operations Research, 1979
- On the ratio of optimal integral and fractional coversDiscrete Mathematics, 1975