TY - JOUR
T1 - An improved approximation algorithm for vertex cover with hard capacities
JF - Journal of Computer and System Sciences
Y1 - 2006
A1 - Gandhi,Rajiv
A1 - Halperin,Eran
A1 - Khuller, Samir
A1 - Kortsarz,Guy
A1 - Srinivasan, Aravind
KW - Approximation algorithms
KW - Capacitated covering
KW - Linear programming
KW - Randomized rounding
KW - Set cover
KW - Vertex cover
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.
VL - 72
SN - 0022-0000
UR - http://www.sciencedirect.com/science/article/pii/S0022000005000747
CP - 1
M3 - 10.1016/j.jcss.2005.06.004
ER -
TY - JOUR
T1 - Approximation algorithms for partial covering problems
JF - Journal of Algorithms
Y1 - 2004
A1 - Gandhi,Rajiv
A1 - Khuller, Samir
A1 - Srinivasan, Aravind
KW - Approximation algorithms
KW - Partial covering
KW - Primal-dual methods
KW - Randomized rounding
KW - Set cover
KW - Vertex cover
AB - 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.
VL - 53
SN - 0196-6774
UR - http://www.sciencedirect.com/science/article/pii/S0196677404000689
CP - 1
M3 - 10.1016/j.jalgor.2004.04.002
ER -
TY - CONF
T1 - Splitters and near-optimal derandomization
T2 - , 36th Annual Symposium on Foundations of Computer Science, 1995. Proceedings
Y1 - 1995
A1 - Naor,M.
A1 - Schulman,L. J
A1 - Srinivasan, Aravind
KW - Boosting
KW - Circuit testing
KW - computational complexity
KW - computational linguistics
KW - Computer science
KW - Contracts
KW - derandomization
KW - deterministic constructions
KW - Educational institutions
KW - Engineering profession
KW - exhaustive testing
KW - fairly general method
KW - fixed-subgraph finding algorithms
KW - hardness of approximation
KW - Information systems
KW - k-restrictions
KW - learning
KW - local-coloring protocol
KW - MATHEMATICS
KW - near-optimal constructions
KW - near-optimal derandomization
KW - Parallel algorithms
KW - probabilistic bound
KW - probability
KW - Protocols
KW - randomised algorithms
KW - Set cover
KW - splitters
AB - We present a fairly general method for finding deterministic constructions obeying what we call k-restrictions; this yields structures of size not much larger than the probabilistic bound. The structures constructed by our method include (n,k)-universal sets (a collection of binary vectors of length n such that for any subset of size k of the indices, all 2k configurations appear) and families of perfect hash functions. The near-optimal constructions of these objects imply the very efficient derandomization of algorithms in learning, of fixed-subgraph finding algorithms, and of near optimal ΣIIΣ threshold formulae. In addition, they derandomize the reduction showing the hardness of approximation of set cover. They also yield deterministic constructions for a local-coloring protocol, and for exhaustive testing of circuits
JA - , 36th Annual Symposium on Foundations of Computer Science, 1995. Proceedings
PB - IEEE
SN - 0-8186-7183-1
M3 - 10.1109/SFCS.1995.492475
ER -