Iterative Partial Rounding for Vertex Cover with Hard Capacities

We provide a simple and novel algorithmic design technique, for which we call iterative partial rounding, that gives a tight rounding-based approximation for vertex cover with hard capacities (VC-HC). In particular, we obtain an f-approximation for VC-HC on hypergraphs, improving over a previous results of Cheung et al. (In: SODA’14, 2014) to the tight extent. This also closes the gap of approximation since it was posted by Chuzhoy and Naor (Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS) 2002, pp. 481--489. IEEE Computer Society, 2002). Our main technical tool for establishing the approximation guarantee is a separation lemma that certifies the existence of a strong partition for solutions that are basic feasible in an extended version of the natural LP. We believe that our rounding technique is of independent interest when hard constraints are considered.