%0 Journal Article
%J Journal of Computer and System Sciences
%D 2006
%T An improved approximation algorithm for vertex cover with hard capacities
%A Gandhi,Rajiv
%A Halperin,Eran
%A Khuller, Samir
%A Kortsarz,Guy
%A Srinivasan, Aravind
%K Approximation algorithms
%K Capacitated covering
%K Linear programming
%K Randomized rounding
%K Set cover
%K Vertex cover
%X 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.
%B Journal of Computer and System Sciences
%V 72
%P 16 - 33
%8 2006/02//
%@ 0022-0000
%G eng
%U http://www.sciencedirect.com/science/article/pii/S0022000005000747
%N 1
%R 10.1016/j.jcss.2005.06.004
%0 Journal Article
%J Journal of Algorithms
%D 2004
%T Approximation algorithms for partial covering problems
%A Gandhi,Rajiv
%A Khuller, Samir
%A Srinivasan, Aravind
%K Approximation algorithms
%K Partial covering
%K Primal-dual methods
%K Randomized rounding
%K Set cover
%K Vertex cover
%X We study a generalization of covering problems called partial covering. Here we wish to cover only a desired number of elements, rather than covering all elements as in standard covering problems. For example, in k-partial set cover, we wish to choose a minimum number of sets to cover at least k elements. For k-partial set cover, if each element occurs in at most f sets, then we derive a primal-dual f-approximation algorithm (thus implying a 2-approximation for k-partial vertex cover) in polynomial time. Without making any assumption about the number of sets an element is in, for instances where each set has cardinality at most three, we obtain an approximation of 4/3. We also present better-than-2-approximation algorithms for k-partial vertex cover on bounded degree graphs, and for vertex cover on expanders of bounded average degree. We obtain a polynomial-time approximation scheme for k-partial vertex cover on planar graphs, and for covering k points in Rd by disks.
%B Journal of Algorithms
%V 53
%P 55 - 84
%8 2004/10//
%@ 0196-6774
%G eng
%U http://www.sciencedirect.com/science/article/pii/S0196677404000689
%N 1
%R 10.1016/j.jalgor.2004.04.002