Capacitated Vertex Covering with Applications
Sudipto Guha, Refael Hassin, Samir Khuller, Einat Or · 2002
In this paper we study the capacitated vertex cover problem, a generalization of the well known vertex cover problem. Given a graph G = (V;E) with weights on the vertices, the goal is to cover all the edges by picking a cover of minimum weight from the vertices. When we pick a copy of a vertex, we pay the weight of the vertex and cover upto a pre-specied number of edges incident on this vertex (its capacity). The problem is NP-hard. We give a primal-dual based 2 approximation and study several generalizations, as well as the problem restricted to trees. 1