New Approximation Algorithms for the Minimimum Set Cover and Other Covering Problems

12^th February 2013, 16:00 G12
Prof. Maxim Sviridenko
Department of Computer Science
University of Warwick
UK

Abstract

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.

Both papers are available on the speaker's website:
http://www2.warwick.ac.uk/fac/sci/dcs/people/Maxim_Sviridenko