Tight approximation for partial vertex cover with hard capacities

DOI10.4230/LIPICS.ISAAC.2017.64MaRDI QIDQ5136285zbMATH OpenOpenAlexFDO

Authors Jia-Yau Shiau, Mong-Jen Kao, Ching-Chi Lin, Der-Tsai Lee

Publication date 25 November 2020

Full work available at URL https://dblp.uni-trier.de/db/conf/isaac/isaac2017.html#ShiauKLL17

zbMATH Keywords

approximation algorithmhard capacitiescapacitated vertex cover

Mathematics Subject Classification ID

Approximation algorithms (68W25) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Tight approximation for partial vertex cover with hard capacities
• Improved algorithms for vertex cover with hard capacities on multigraphs and hypergraphs
• \(O(f)\) bi-criteria approximation for capacitated covering with hard capacities
• \(O(f)\) bi-approximation for capacitated covering with hard capacities
• Tight algorithms for vertex cover with hard capacities on multigraphs and hypergraphs

Cites work

• A Primal-Dual Bicriteria Distributed Algorithm for Capacitated Vertex Cover
• A primal-dual approximation algorithm for partial vertex cover: Making educated guesses
• An improved approximation algorithm for vertex cover with hard capacities
• Approximation of Partial Capacitated Vertex Cover
• Capacitated vertex covering
• Covering Problems with Hard Capacities
• Improved algorithms for vertex cover with hard capacities on multigraphs and hypergraphs
• Iterative partial rounding for vertex cover with hard capacities
• LP-based algorithms for capacitated facility location
• Set cover revisited: hypergraph cover with hard capacities
• Tight algorithms for vertex cover with hard capacities on multigraphs and hypergraphs
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• \(O(f)\) bi-approximation for capacitated covering with hard capacities

Cited in

(11)

• Tight gaps for vertex cover in the Sherali-Adams SDP hierarchy
• Iterative partial rounding for vertex cover with hard capacities
• An improved approximation algorithm for vertex cover with hard capacities
• Tight algorithms for vertex cover with hard capacities on multigraphs and hypergraphs
• Improved algorithms for vertex cover with hard capacities on multigraphs and hypergraphs
• Iterative partial rounding for vertex cover with hard capacities
• Approximation of Partial Capacitated Vertex Cover
• On hard instances of approximate vertex cover
• \(O(f)\) bi-approximation for capacitated covering with hard capacities
• Tight approximation for partial vertex cover with hard capacities
• Approximation of Partial Capacitated Vertex Cover

This page was built for publication: Tight approximation for partial vertex cover with hard capacities

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5136285)