TY - GEN

T1 - Capacitated vertex covering with applications

AU - Guha, Sudipto

AU - Hassin, Refael

AU - Khuller, Samir

AU - Or, Einat

PY - 2002/1/1

Y1 - 2002/1/1

N2 - 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-specified 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.

AB - 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-specified 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.

UR - http://www.scopus.com/inward/record.url?scp=84902074040&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84902074040&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84902074040

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 858

EP - 865

BT - Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002

PB - Association for Computing Machinery

T2 - 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002

Y2 - 6 January 2002 through 8 January 2002

ER -