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 \)
- Approximation algorithm for vertex cover with multiple covering constraints
- 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
- \(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
- Approximation of Partial Capacitated Vertex Cover
- Set cover revisited: hypergraph cover with hard capacities
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)
