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

DOI10.1007/s00453-018-0506-6zbMath1421.68232OpenAlexW2888603221WikidataQ129348481 ScholiaQ129348481MaRDI 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 capacitiesbi-criteria approximationcapacitated covering

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items (1)

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

This page was built for publication: \(O(f)\) bi-criteria approximation for capacitated covering with hard capacities