Online interval scheduling : randomized and multiprocessor cases
Research output: Journal Publications and Reviews (RGC: 21, 22, 62) › 21_Publication in refereed journal › peer-review
Author(s)
Related Research Unit(s)
Detail(s)
| Original language | English |
|---|---|
| Pages (from-to) | 248-262 |
| Journal / Publication | Journal of Combinatorial Optimization |
| Volume | 16 |
| Issue number | 3 |
| Online published | 5 Jan 2008 |
| Publication status | Published - Oct 2008 |
Link(s)
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 journal › peer-review
