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


In the Preemptive Generalized Min Sum Set Cover Problem, we are given n ground elements and a collection of sets {S1, S2, ..., Sm} where each subset Si of ground elements has a positive requirement ki that has to be fulfilled. We would like to preemptively order (schedule) all elements to minimize the total cover time of all sets Si. The cover time of set Si is defined as the first time when ki amount of elements in Si 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" [...]


  Payday Loans In Indiana. In rare cases, the smarting in eyes, the tumefaction of eyelids, nausea and headaches can happen. In case of long term Levitra Soft online administration the side effects become less perceptible or disappear at all.