An improved approximation algorithm for vertex cover with hard capacities
DOI10.1016/j.jcss.2005.06.004zbMath1105.68089OpenAlexW2029933769MaRDI QIDQ2581755
Samir Khuller, Aravind Srinivasan, Rajiv Gandhi, Eran Halperin, Guy Kortsarz
Publication date: 10 January 2006
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2005.06.004
Linear programmingRandomized roundingVertex coverApproximation algorithmsSet coverCapacitated covering
Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (18)
Cites Work
- Approximation algorithms for combinatorial problems
- Generalized submodular cover problems and applications
- An analysis of the greedy algorithm for the submodular set covering problem
- A Greedy Heuristic for the Set-Covering Problem
- Heuristics for the fixed cost median problem
- Approximation Algorithms for the Set Covering and Vertex Cover Problems
- Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: An improved approximation algorithm for vertex cover with hard capacities