Online interval scheduling : randomized and multiprocessor cases

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

20 Scopus Citations
View graph of relations

Author(s)

  • Stanley P.Y. Fung
  • Chung Keung Poon
  • Feifeng Zheng

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)248-262
Journal / PublicationJournal of Combinatorial Optimization
Volume16
Issue number3
Online published5 Jan 2008
Publication statusPublished - Oct 2008

Abstract

We consider the problem of scheduling a set of equal-length intervals arriving online, where each interval is associated with a weight and the objective is to maximize the total weight of completed intervals. An optimal 4-competitive algorithm has long been known in the deterministic case, but the randomized case remains open. We give the first randomized algorithm for this problem, achieving a competitive ratio of 3.5822. We also prove a randomized lower bound of 4/3, which is an improvement over the previous 5/4 result. Then we show that the techniques can be carried to the deterministic multiprocessor case, giving a 3.5822-competitive 2-processor algorithm, and a 4/3 lower bound for any number of processors. We also give a lower bound of 2 for the case of two processors.

Research Area(s)

  • Intervals, Online algorithms, Randomization, Scheduling

Citation Format(s)

Online interval scheduling : randomized and multiprocessor cases. / Fung, Stanley P.Y.; Poon, Chung Keung; Zheng, Feifeng.

In: Journal of Combinatorial Optimization, Vol. 16, No. 3, 10.2008, p. 248-262.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review