About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
STACS 2012
Conference paper
Preemptive and non-preemptive Generalized Min Sum Set Cover
Abstract
In the (non-preemptive) Generalized Min Sum Set Cover Problem, we are given n ground elements and a collection of sets S = {S1, S 2,⋯, Sm} where each set Si ε 2 |n| has a positive requirement k(Si) 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 Si is defined as the first index j in the ordering such that the first j elements in the ordering contain k(Si) elements in Si. This problem was introduced by [1] with interesting motivations in web page ranking and broadcast scheduling. For this problem, constant approximations are known [2, 15]. 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 [2, 15]. 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. © Sungjin Im, Maxim Sviridenko and Ruben van der Zwaan.