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

zbMATH Keywords

Linear programmingRandomized roundingVertex coverApproximation algorithmsSet coverCapacitated covering

Mathematics Subject Classification ID

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)

Tight approximation for partial vertex cover with hard capacities ⋮ Tight approximation for partial vertex cover with hard capacities ⋮ Capacitated covering problems in geometric spaces ⋮ Capacitated Domination and Covering: A Parameterized Perspective ⋮ Primal-Dual Schema for Capacitated Covering Problems ⋮ Improved bounds for metric capacitated covering problems ⋮ Unnamed Item ⋮ Iterative partial rounding for vertex cover with hard capacities ⋮ Capacitated Domination Problem ⋮ A model for minimizing active processor time ⋮ \(O(f)\) bi-criteria approximation for capacitated covering with hard capacities ⋮ Capacitated domination problem ⋮ Dynamic programming based algorithms for set multicover and multiset multicover problems ⋮ The multi‐integer set cover and the facility terminal cover problem ⋮ Capacitated discrete unit disk cover ⋮ Primal-dual schema for capacitated covering problems ⋮ Capacitated Covering Problems in Geometric Spaces ⋮ Capacitated domination: problem complexity and approximation algorithms

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