TY - JOUR
T1 - Capacitated vertex covering
AU - Guha, Sudipto
AU - Hassin, Refael
AU - Khuller, Samir
AU - Or, Einat
N1 - Funding Information:
✩ An extended abstract of this work appeared in ACM–SIAM Symposium on Discrete Algorithms (SODA) 2002. * Corresponding author. E-mail addresses: sudipto@cis.upenn.edu (S. Guha), hassin@post.tau.ac.il (R. Hassin), samir@cs.umd.edu (S. Khuller), eior@post.tau.ac.il (E. Or). 1 The work was done while the author was at AT&T Research, Florham Park, NJ 07932. 2 Research supported by NSF Awards CCR-9820965 and CCR-0113192.
PY - 2003/8
Y1 - 2003/8
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 up to a pre-specified number of edges incident on this vertex (its capacity). The problem is NP-hard. We give a primal-dual based approximation algorithm with an approximation guarantee of 2, 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 up to a pre-specified number of edges incident on this vertex (its capacity). The problem is NP-hard. We give a primal-dual based approximation algorithm with an approximation guarantee of 2, and study several generalizations, as well as the problem restricted to trees.
KW - Approximation algorithm
KW - Capacitated network design
KW - Vertex cover
UR - http://www.scopus.com/inward/record.url?scp=0041426751&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0041426751&partnerID=8YFLogxK
U2 - 10.1016/S0196-6774(03)00053-1
DO - 10.1016/S0196-6774(03)00053-1
M3 - Article
AN - SCOPUS:0041426751
SN - 0196-6774
VL - 48
SP - 257
EP - 270
JO - Journal of Algorithms
JF - Journal of Algorithms
IS - 1
ER -