SeminarsView all Seminars | Download ICal for this event
Min Sum Set Cover and Tail Bounds for Sums of Bernoullis
Series: Theory Seminar
Speaker: Dr. Jatin Batra, Reader, School of Technology and Computer Science, TIFR Mumbai
Date/Time: Nov 12 16:00:00
Location: Microsoft Teams - ON-LINE
We study the generalized min sum set cover (GMSSC) problem, wherein given a collection of hyperedges E with arbitrary covering requirements, the goal is to find an ordering of the vertices to minimize the total cover time of the hyperedges. We give a 4.642 approximation algorithm for GMSSC, coming close to the best possible bound of 4, improving the previous best bound of 12 by Im, Sviridenko and van der Zwaan. For the special case when the hypergraph is a graph, we give a 16/9 approximation, improving the previous best bound of 1.999946 by Barenholz and Feige. Our algorithms are based on applying a suitable linear transformation on the LP solution and applying randomized rounding.
As part of the analysis of our algorithm, we also derive an inequality on the lower tail of a sum of independent Bernoulli random variables, which might be of independent interest and broader utility. Specifically, we show how to get better tail bounds than Chernoff when the deviation from the mean is very small.
We also give a new dual-fitting analysis for min sum set cover, giving tight (upto NP-hardness) bound of (p+1)1+1/p(p+1)1+1/p for the â„“pâ„“p norm of cover times.
Microsoft Teams Link:
For more details about the seminar please visit the website at https://www.csa.iisc.ac.in/iisc-msr-seminar/
Host Faculty: Dr. Arindam Khan