Preemptive and non-preemptive generalized min sum set cover

S. Im, M. Sviridenko, G.R.J. Zwaan, van der

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Abstract

In the (non-preemptive) Generalized Min Sum Set Cover Problem, we are given n ground elements and a collection of sets S = {S_1, S_2, ..., S_m} where each set S_i in 2^{[n]} has a positive requirement k(S_i) that has to be fulfilled. We would like to order all elements to minimize the total (weighted) cover time of all sets. The cover time of a set S_i is defined as the first index j in the ordering such that the first j elements in the ordering contain k(S_i) elements in S_i. This problem was introduced by [Azar, Gamzu and Yin, 2009] with interesting motivations in web page ranking and broadcast scheduling. For this problem, constant approximations are known [Bansal, Gupta and Krishnaswamy, 2010][Skutella and Williamson, 2011]. We study the version where preemption is allowed. The difference is that elements can be fractionally scheduled and a set S is covered in the moment when k(S) amount of elements in S are scheduled. We give a 2-approximation for this preemptive problem. Our linear programming and analysis are completely different from [Bansal, Gupta and Krishnaswamy, 2010][Skutella and Williamson, 2011]. 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 problem. Keywords: Set Cover, Approximation, Preemption, Latency, Average cover time
Original languageEnglish
Title of host publication29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)
EditorsC. Dürr, T. Wilke
Place of PublicationDagstuhl
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages465-476
ISBN (Print)978-3-939897-35-4
DOIs
Publication statusPublished - 2012
Externally publishedYes

Publication series

NameLIPIcs: Leibniz International Proceedings in Informatics
Volume14
ISSN (Print)1868-8968

Fingerprint Dive into the research topics of 'Preemptive and non-preemptive generalized min sum set cover'. Together they form a unique fingerprint.

Cite this