2016/06/25 by Sam Chiu-wai Wong, Wong, Sam Chiu-wai
Computer Science · Engineering · #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Packing Problems
paper · pdf · doi:10.48550/arxiv.1606.07861
openalex publication_date 2016/06/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 the problem with ideas coming from several previous works. We also give a faster implementation of the method based on certain iteratively rounding the solution to certain CGW-style covering LPs. We note that independent of this work, Kao [#kao2017iterative] also recently obtained the same result.