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 algorithmcapacitated vertex coverhard capacities

Mathematics Subject Classification ID

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

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

• O(f) bi-approximation for capacitated covering with hard capacities
• A primal-dual approximation algorithm for partial vertex cover: Making educated guesses
• A Primal-Dual Bicriteria Distributed Algorithm for Capacitated Vertex Cover
• 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 \)

Cited in

(13)

• O(f) bi-criteria approximation for capacitated covering with hard capacities
• Iterative partial rounding for vertex cover with hard capacities
• Tight approximation for partial vertex cover with hard capacities
• An improved approximation algorithm for vertex cover with hard capacities
• Tight gaps for vertex cover in the Sherali-Adams SDP hierarchy
• Tight algorithms for vertex cover with hard capacities on multigraphs and hypergraphs
• Iterative partial rounding for vertex cover with hard capacities
• O(f) bi-approximation for capacitated covering with hard capacities
• On hard instances of approximate vertex cover
• Improved algorithms for vertex cover with hard capacities on multigraphs and hypergraphs
• Approximation of Partial Capacitated Vertex Cover
• Approximation of Partial Capacitated Vertex Cover
• FPT approximation using treewidth: capacitated vertex cover, target set selection and vector dominating set

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)