TY - GEN
T1 - Online Interval Scheduling
T2 - 13th Annual International Computing and Combinatorics Conference (COCOON 2007)
AU - Fung, Stanley P.Y.
AU - Poon, Chung Keung
AU - Zheng, Feifeng
PY - 2007/7
Y1 - 2007/7
N2 - 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.618. We also prove a randomized lower bound of 4/3, which is an improvement over the previous 5/4 result, and a lower bound of 2 for a class of barely random algorithms which include our new algorithm. We also show that the techniques can be carried to the deterministic multiprocessor case, giving a 3.618-competitive 2-processor algorithm, a 5/4 lower bound for any number of processors, and a 2 lower bound for 2 processors.
AB - 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.618. We also prove a randomized lower bound of 4/3, which is an improvement over the previous 5/4 result, and a lower bound of 2 for a class of barely random algorithms which include our new algorithm. We also show that the techniques can be carried to the deterministic multiprocessor case, giving a 3.618-competitive 2-processor algorithm, a 5/4 lower bound for any number of processors, and a 2 lower bound for 2 processors.
UR - http://www.scopus.com/inward/record.url?scp=37849045000&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-37849045000&origin=recordpage
U2 - 10.1007/978-3-540-73545-8_19
DO - 10.1007/978-3-540-73545-8_19
M3 - RGC 32 - Refereed conference paper (with host publication)
SN - 9783540735441
SN - 3540735445
T3 - Lecture Notes in Computer Science
SP - 176
EP - 186
BT - Computing and Combinatorics
PB - Springer Verlag
Y2 - 16 July 2007 through 19 July 2007
ER -