Tight approximation for partial vertex cover with hard capacities
From MaRDI portal
Publication:5136285
DOI10.4230/LIPICS.ISAAC.2017.64zbMATH Open1457.68312OpenAlexW2784095499MaRDI QIDQ5136285FDOQ5136285
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
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 \)
- Capacitated vertex covering
- LP-Based Algorithms for Capacitated Facility Location
- 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
- A primal-dual approximation algorithm for partial vertex cover: Making educated guesses
- 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 Q5136285)
