Tight approximation for partial vertex cover with hard capacities

DOI10.1016/J.TCS.2019.01.027MaRDI QIDQ2420573zbMATH OpenOpenAlexWikidataFDO

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

Publication date 6 June 2019

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2017/8269/

zbMATH Keywords

approximation algorithmpartial coverhard capacitycapacitated 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 algorithm for vertex cover with multiple covering constraints
• Approximation algorithms for the partition vertex cover problem
• Approximation of Partial Capacitated Vertex Cover
• Capacitated domination problem
• Capacitated domination: problem complexity and approximation algorithms
• 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
• 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

(13)

• Tight gaps for vertex cover in the Sherali-Adams SDP hierarchy
• Tight approximation for partial vertex cover with hard capacities
• Iterative partial rounding for vertex cover with hard capacities
• An improved approximation algorithm for vertex cover with hard capacities
• 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
• Approximation algorithm for vertex cover with multiple covering constraints
• Approximation algorithm for vertex cover with multiple covering constraints
• On hard instances of approximate vertex cover
• \(O(f)\) bi-approximation for capacitated covering with hard capacities
• Set cover revisited: hypergraph 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 Q2420573)