2026-07-20T05:27:52Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3399 2024-03-06T10:34:13Z ddc:004 open_access

Preemptive and Non-Preemptive Generalized Min Sum Set Cover Im, Sungjin Sviridenko, Maxim van der Zwaan, Ruben Set Cover Approximation Preemption Latency Average cover time 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sungjin Im and Maxim Sviridenko and Ruben van der Zwaan 2012 Is Part Of LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2012.465 urn:nbn:de:0030-drops-33991 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.465 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode