License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2011.472
URN: urn:nbn:de:0030-drops-30363
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2011/3036/
Go to the corresponding LIPIcs Volume Portal

Halldorsson, Magnus M. ; Patt-Shamir, Boaz ; Rawitz, Dror

Online Scheduling with Interval Conflicts

pdf-format:
44.pdf (0.7 MB)

Abstract

In the problem of Scheduling with Interval Conflicts, there is a ground set of items indexed by integers, and the input is a collection of conflicts, each containing all the items whose index lies within some interval on the real line. Conflicts arrive in an online fashion. A scheduling algorithm must select, from each conflict, at most one survivor item, and the goal is to maximize the number (or weight) of items that survive all the conflicts they are involved in. We present a centralized deterministic online algorithm whose competitive ratio is O(log sigma), where sigma is the size of the largest conflict. For the distributed setting, we present another deterministic algorithm whose competitive ratio is 2 log sigma, in the special contiguous case, in which the item indices constitute a contiguous interval of integers. Our upper bounds are complemented by two lower bounds: one that shows that even in the contiguous case, all deterministic algorithms (centralized or distributed) have competitive ratio Omega(log sigma), and that in the non-contiguous case, no deterministic oblivious algorithm (i.e., a distributed algorithm that does not use communication) can have a bounded competitive ratio.

BibTeX - Entry

@InProceedings{halldorsson_et_al:LIPIcs:2011:3036,
  author =	{Magnus M. Halldorsson and Boaz Patt-Shamir and Dror Rawitz},
  title =	{{Online Scheduling with Interval Conflicts}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011) },
  pages =	{472--483},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Thomas Schwentick and Christoph D{\"u}rr},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2011/3036},
  URN =		{urn:nbn:de:0030-drops-30363},
  doi =		{10.4230/LIPIcs.STACS.2011.472},
  annote =	{Keywords: online scheduling, online set packing, interval conflicts, competitive analysis, compound tasks, distributed algorithms}
}

Keywords: online scheduling, online set packing, interval conflicts, competitive analysis, compound tasks, distributed algorithms
Collection: 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)
Issue Date: 2011
Date of publication: 11.03.2011

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI