Tight Algorithms for Vertex Cover with Hard Capacities on Multigraphs and Hypergraphs

DOI10.1137/1.9781611974782.173zbMath1411.68200arXiv1606.07861OpenAlexW2952555928MaRDI QIDQ4575922

Sam Chiu-wai Wong

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1606.07861

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25)

Related Items (8)

Tight approximation for partial vertex cover with hard capacities ⋮ Tight approximation for partial vertex cover with hard capacities ⋮ Capacitated covering problems in geometric spaces ⋮ Improved bounds for metric capacitated covering problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ \(O(f)\) bi-criteria approximation for capacitated covering with hard capacities ⋮ Capacitated Covering Problems in Geometric Spaces

This page was built for publication: Tight Algorithms for Vertex Cover with Hard Capacities on Multigraphs and Hypergraphs