
180 Park Ave - Building 103
Florham Park, NJ
http://public.research.att.com/~barna/
Subject matter expert in Algorithms, Probabilistic Methods, Databases
Her research interest spans several areas of Theoretical Computer Science (TCS) and Databases. Specifically, under TCS, she works on algorithm design and analysis, hardness of approximation, probabilistic methods and combinatorial optimization. In Databases, her major focus is on research related to data quality, data integration and distributed data management such as in cloud.
Set Cover revisited: Hypergraph Cover with Hard Capacities
Barna Saha, Samir Khuller
International Colloquium on Automata, Languages, and Programming (ICALP),
2012.
[PDF]
[BIB]
Springer-Verlag Copyright
The definitive version was published in 2012. , 2012-07-13
{In this paper, we consider generalizations of classical covering problems to handle hard capacities. In the hard capacitated set cover problem, additionally each set has a covering capacity which we are not allowed to exceed.
In other words, after picking a set, we may cover at most a specified number of
elements. Based on the classical results by Wolsey, an O(log n) approximation
follows for this problem.
Chuzhoy and Naor [FOCS 2002], first studied the special case of unweighted
vertex cover with hard capacities and developed an elegant 3 approximation for
it based on rounding a natural LP relaxation. This was subsequently improved to
a 2 approximation by Gandhi et al. [ICALP 2003]. These results are surprising in
light of the fact that for weighted vertex cover with hard capacities, the problem is
at least as hard as set cover to approximate. Hence this separates the unweighted
problem from the weighted version.
The set cover hardness precludes the possibility of a constant factor approximation for the hard-capacitated vertex cover problem on weighted graphs. However, it was not known whether a better than logarithmic approximation is possible on unweighted multigraphs, i.e., graphs that may contain parallel edges. Neither the approach of Chuzhoy and Naor, nor the follow-up work of Gandhi et al. can handle the case of multigraphs. In fact, achieving a constant factor approximation for hard-capacitated vertex cover problem on unweighted multigraphs was posed as an open question in Chuzhoy and Naor’s work. In this paper, we resolve this question by providing the first constant factor approximation algorithm for the vertex cover problem with hard capacities on unweighted multigraphs. Previous works cannot handle hypergraphs which is analogous to consider set systems where elements belong to at most f sets. In this paper, we give an O(f) approximation algorithm for this problem. Further, we extend these works to consider partial covers.}