Tight approximation for partial vertex cover with hard capacities
DOI10.1016/J.TCS.2019.01.027zbMATH Open1423.68594OpenAlexW2914968681WikidataQ128539943 ScholiaQ128539943MaRDI QIDQ2420573FDOQ2420573
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/
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
Approximation algorithms (68W25) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Title not available (Why is that?)
- Capacitated vertex covering
- A Primal-Dual Bicriteria Distributed Algorithm for Capacitated Vertex Cover
- An improved approximation algorithm for vertex cover with hard capacities
- Set Cover Revisited: Hypergraph Cover with Hard Capacities
- Covering Problems with Hard Capacities
- Capacitated domination problem
- A primal-dual approximation algorithm for partial vertex cover: Making educated guesses
- Approximation algorithms for the partition vertex cover problem
- Capacitated domination: problem complexity and approximation algorithms
- 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
- Title not available (Why is that?)
Cited In (5)
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)
