Tight approximation for partial vertex cover with hard capacities
From MaRDI portal
Publication:5136285
DOI10.4230/LIPIcs.ISAAC.2017.64zbMath1457.68312OpenAlexW2784095499MaRDI QIDQ5136285
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
Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25)
Cites Work
- Unnamed Item
- 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
- LP-Based Algorithms for Capacitated Facility Location
- 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
This page was built for publication: Tight approximation for partial vertex cover with hard capacities
