Improved Algorithms for Vertex Cover with Hard Capacities on Multigraphs and Hypergraphs
From MaRDI portal
Publication:5384086
DOI10.1137/1.9781611973402.124zbMath1421.68203OpenAlexW2477603932MaRDI QIDQ5384086
Michel X. Goemans, Sam Chiu-wai Wong, Wang-Chi Cheung
Publication date: 20 June 2019
Published in: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/1.9781611973402.124
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items
Tight approximation for partial vertex cover with hard capacities, Tight approximation for partial vertex cover with hard capacities, Iterative partial rounding for vertex cover with hard capacities, \(O(f)\) bi-criteria approximation for capacitated covering with hard capacities, Parameterized certificate dispersal and its variants
