Maxim Sviridenko
Warwick
New Approximation Algorithms for the Minimimum Set Cover and Other
Covering Problems
We study the relationship between the approximation factor for the
Set-Cover problem and the parameters $\Delta$ : the maximum cardinality of
any subset, and $k$ : the maximum number of subsets containing any element
of the ground set. We show an LP rounding based approximation of
$(k-1)(1-e^{-\frac{\ln \Delta}{k-1}}) +1$, which is substantially better
than the classical algorithms in the range $k \approx \ln \Delta$, and
also improves on related previous works [Krivelevich, Okun]. For the
interesting case when $k = \theta(\log \Delta)$ we also exhibit an
integrality gap which essentially matches our approximation algorithm. In
addition we will discuss results on Generalized Min Sum Set Cover Problem.
I will describe the state of the art, our results and open problems.