Tight approximation for partial vertex cover with hard capacities

DOI10.1016/j.tcs.2019.01.027zbMath1423.68594OpenAlexW2914968681WikidataQ128539943 ScholiaQ128539943MaRDI QIDQ2420573

Jia-Yau Shiau, Ching-Chi Lin, Mong-Jen Kao, 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

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

Cites Work

• Unnamed Item
• Unnamed Item
• Capacitated domination problem
• Approximation algorithms for the partition vertex cover problem
• Capacitated domination: problem complexity and approximation algorithms
• A primal-dual approximation algorithm for partial vertex cover: Making educated guesses
• 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
• 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