Tight Algorithms for Vertex Cover with Hard Capacities on Multigraphs and Hypergraphs
Sam Chiu-wai Wong · 2017
In this paper we give a f-approximation algorithm for the minimum unweighted Vertex Cover problem with Hard Capacity constraints (VCHC) on f-hypergraphs. This problem generalizes standard vertex cover for which the best known approximation ratio is also f and cannot be improved assuming the unique game conjecture. Our result is therefore essentially the best possible. This improves over the previous 2.155 (for f = 2) and 2f approximation algorithms by Cheung, Goemans and Wong (CGW). At the heart of our approach is to apply iterative rounding to a natural LP relaxation that is slightly different from prior works which used (non-iterative) rounding. Our algorithm is significantly simpler and offers an intuitive explanation why f-approximation can be achieved for VCHC. We also present faster implementations of our method based on iteratively rounding the solution to certain CGW-style covering LPs.