BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260921T091919Z
UID:Seminar-dept-311@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20130212T160000
DTEND:20130212T170000
SUMMARY:School Seminar Series
DESCRIPTION:Prof. Maxim Sviridenko: New Approximation Algorithms for the Minimimum Set Cover and Other Covering Problems\n\nWe 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.\n\n\n\nIn 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.\n\n\n\nBoth papers are available on the speaker's website:\nhttp://www2.warwick.ac.uk/fac/sci/dcs/people/Maxim_Sviridenko\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=311
LOCATION:G12
END:VEVENT
END:VCALENDAR