O(f) Bi-Approximation for Capacitated Covering with Hard Capacities

Mong-Jen Kao, Hai-Lun Tu, D. T. Lee

We consider capacitated vertex cover with hard capacity constraints (VC-HC) on hypergraphs. In this problem we are given a hypergraph $G=(V,E)$ with a maximum edge size $f$. Each e…