1 Search Results for "van der Zwaan, Ruben"

Document
DOI: 10.4230/LIPIcs.STACS.2012.465
Preemptive and Non-Preemptive Generalized Min Sum Set Cover

Authors: Sungjin Im, Maxim Sviridenko, and Ruben van der Zwaan

Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

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.
Cite as

Sungjin Im, Maxim Sviridenko, and Ruben van der Zwaan. Preemptive and Non-Preemptive Generalized Min Sum Set Cover. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 465-476, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{im_et_al:LIPIcs.STACS.2012.465,
  author =	{Im, Sungjin and Sviridenko, Maxim and van der Zwaan, Ruben},
  title =	{{Preemptive and Non-Preemptive Generalized Min Sum Set Cover}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{465--476},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{D\"{u}rr, Christoph and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.465},
  URN =		{urn:nbn:de:0030-drops-33991},
  doi =		{10.4230/LIPIcs.STACS.2012.465},
  annote =	{Keywords: Set Cover, Approximation, Preemption, Latency, Average cover time}
}
  • Refine by Author
  • 1 Im, Sungjin
  • 1 Sviridenko, Maxim
  • 1 van der Zwaan, Ruben

  • Refine by Classification

  • Refine by Keyword
  • 1 Approximation
  • 1 Average cover time
  • 1 Latency
  • 1 Preemption
  • 1 Set Cover

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2012

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact