\(O(f)\) bi-criteria approximation for capacitated covering with hard capacities

DOI10.1007/s00453-018-0506-6zbMath1421.68232MaRDI QIDQ1741845

Hai-Lun Tu, Mong-Jen Kao, Der-Tsai Lee

Publication date: 7 May 2019

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-018-0506-6

zbMATH Keywords

hard capacities; bi-criteria approximation; capacitated covering

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

68W25: Approximation algorithms

Related Items

Iterative partial rounding for vertex cover with hard capacities

Cites Work

• Capacitated domination problem
• An analysis of the greedy algorithm for the submodular set covering problem
• Capacitated domination: problem complexity and approximation algorithms
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• An improved approximation algorithm for vertex cover with hard capacities
• Set Cover Revisited: Hypergraph Cover with Hard Capacities
• Covering Problems with Hard Capacities
• A Primal-Dual Bicriteria Distributed Algorithm for Capacitated Vertex Cover
• A linear-time approximation algorithm for the weighted vertex cover problem
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Capacitated vertex covering
• Tight Algorithms for Vertex Cover with Hard Capacities on Multigraphs and Hypergraphs
• Iterative Partial Rounding for Vertex Cover with Hard Capacities
• Improved Algorithms for Vertex Cover with Hard Capacities on Multigraphs and Hypergraphs
• Approximation of Partial Capacitated Vertex Cover