An Improved Approximation Algorithm For Vertex Cover with Hard Capacities

Abstract

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)$, the goal is to cover all the edges by picking a minimum cover using the vertices. When we pick a vertex, we 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, $2$-approximation algorithms were developed with the assumption that multiple copies of a vertex may be chosen in the cover. If we are allowed to pick at most a given number of copies of each vertex, then the problem is significantly harder to solve. Chuzhoy and Naor (\textit{Proc.\ IEEE Symposium on Foundations of Computer Science, 481--489, 2002}) have recently shown that the weighted version of this problem is at least as hard as set cover; they have also 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 $3$ and matching (up to lower-order terms) the best approximation ratio known for the vertex cover problem. UMIACS-TR-2003-30