TY - JOUR
T1 - Online interval scheduling
T2 - randomized and multiprocessor cases
AU - Fung, Stanley P.Y.
AU - Poon, Chung Keung
AU - Zheng, Feifeng
PY - 2008/10
Y1 - 2008/10
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.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.
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.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.
KW - Intervals
KW - Online algorithms
KW - Randomization
KW - Scheduling
UR - http://www.scopus.com/inward/record.url?scp=49749134384&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-49749134384&origin=recordpage
U2 - 10.1007/s10878-007-9131-z
DO - 10.1007/s10878-007-9131-z
M3 - 21_Publication in refereed journal
VL - 16
SP - 248
EP - 262
JO - Journal of Combinatorial Optimization
JF - Journal of Combinatorial Optimization
SN - 1382-6905
IS - 3
ER -