TY - JOUR

T1 - An improved approximation algorithm for vertex cover with hard capacities

AU - Gandhi, Rajiv

AU - Halperin, Eran

AU - Khuller, Samir

AU - Kortsarz, Guy

AU - Srinivasan, Aravind

N1 - Funding Information:
A preliminary version of this work appeared in the Proceedings of the International Colloquium on Automata, Languages, and Programming, 2003, pp. 164–175. ∗Corresponding author. Department of Computer Science, University of Maryland, College Park, MD 20742, USA. E-mail addresses: rajivg@camden.rutgers.edu (R. Gandhi), eran@cs.berkeley.edu (E. Halperin), samir@cs.umd.edu (S. Khuller), guyk@camden.rutgers.edu (G. Kortsarz), srin@cs.umd.edu (A. Srinivasan). 1Part of this work was done while the author was a student at the University of Maryland, College Park and was supported by NSF Award CCR-9820965. 2 Supported in part by NSF Grants CCR-9820951 and CCR-0121555 and DARPA cooperative agreement F30602-00-2-0601. 3This research was supported by NSF Awards CCF-0430650 and CCR-0113192. 4This material is based upon work supported in part by the National Science Foundation under Grants 0208005 and CNS-0426683.

PY - 2006/2

Y1 - 2006/2

N2 - We study the capacitated vertex cover problem, a generalization of the well-known vertex-cover problem. Given a graph G=(V,E), the goal is to cover all the edges by picking a minimum cover using the vertices. When we pick a vertex, we can cover up to a pre-specified number of edges incident on this vertex (its capacity). The problem is clearly NP-hard as it generalizes the well-known vertex-cover problem. Previously, approximation algorithms with an approximation factor of 2 were developed with the assumption that an arbitrary number of copies of a vertex may be chosen in the cover. If we are allowed to pick at most a fixed number of copies of each vertex, the approximation algorithm becomes much more complex. Chuzhoy and Naor (FOCS, 2002) have shown that the weighted version of this problem is at least as hard as set cover; in addition, they developed a 3-approximation algorithm for the unweighted version. We give a 2-approximation algorithm for the unweighted version, improving the Chuzhoy-Naor bound of three and matching (up to lower-order terms) the best approximation ratio known for the vertex-cover problem.

AB - We study the capacitated vertex cover problem, a generalization of the well-known vertex-cover problem. Given a graph G=(V,E), the goal is to cover all the edges by picking a minimum cover using the vertices. When we pick a vertex, we can cover up to a pre-specified number of edges incident on this vertex (its capacity). The problem is clearly NP-hard as it generalizes the well-known vertex-cover problem. Previously, approximation algorithms with an approximation factor of 2 were developed with the assumption that an arbitrary number of copies of a vertex may be chosen in the cover. If we are allowed to pick at most a fixed number of copies of each vertex, the approximation algorithm becomes much more complex. Chuzhoy and Naor (FOCS, 2002) have shown that the weighted version of this problem is at least as hard as set cover; in addition, they developed a 3-approximation algorithm for the unweighted version. We give a 2-approximation algorithm for the unweighted version, improving the Chuzhoy-Naor bound of three and matching (up to lower-order terms) the best approximation ratio known for the vertex-cover problem.

KW - Approximation algorithms

KW - Capacitated covering

KW - Linear programming

KW - Randomized rounding

KW - Set cover

KW - Vertex cover

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

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

U2 - 10.1016/j.jcss.2005.06.004

DO - 10.1016/j.jcss.2005.06.004

M3 - Article

AN - SCOPUS:27844458002

VL - 72

SP - 16

EP - 33

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

SN - 0022-0000

IS - 1

ER -