**Wednesday, 15:45 - 16:10 h, Room: H 3010**

**Sungjin Im**

Preemptive and non-preemptive generalized min sum set cover

**Coauthors: Maxim Sviridenko, Ruben van der Zwaan**

**Abstract:**

In the Preemptive Generalized Min Sum Set Cover Problem, we are given n ground elements and a collection of sets {S_{1}, S_{2}, ..., S_{m}} where each subset S_{i} of ground elements has a positive requirement k_{i} that has to be fulfilled. We would like to preemptively order (schedule) all elements to minimize the total cover time of all sets S_{i}. The cover time of set S_{i} is defined as the first time when k_{i} amount of elements in S_{i} are scheduled. We give a 2-approximation for this problem, which is tight under a certain complexity assumption. We also show that any preemptive solution can be transformed into a non-preemptive one by losing a factor of 6.2 in the objective function. As a byproduct, we obtain an improved 12.4-approximation for the non-preemptive version of this problem. A key technical ingredient of our results is a novel linear programming relaxation which is completely different from [Bansal-Gupta-Krishnaswamy 10], [Skutella-Williamson 11]. We also show that our relaxation is stronger than the previous one.

Talk 2 of the invited session Wed.3.H 3010

**"Randomized rounding algorithms in mathematical programming"** [...]

Cluster 1

**"Approximation & online algorithms"** [...]