Iterative Partial Rounding for Vertex Cover with Hard Capacities

DOI10.1137/1.9781611974782.174zbMath1411.68196OpenAlexW2468125873MaRDI QIDQ4575923

Mong-Jen Kao

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://doi.org/10.1137/1.9781611974782.174

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: Iterative Partial Rounding for Vertex Cover with Hard Capacities