TY - JOUR
T1 - Priority algorithms for makespan minimization in the subset model
AU - Regev, Oded
N1 - Funding Information:
✩ Research supported in part by NSF grant CCR-9987845. E-mail address: [email protected] (O. Regev).
Copyright:
Copyright 2008 Elsevier B.V., All rights reserved.
PY - 2002/11/15
Y1 - 2002/11/15
N2 - We continue the recent study of priority algorithms initiated by Borodin et al. [Proc. 13th ACM-SIAM Symp. on Discrete Algorithms, 2002, pp. 752-761]. The definition of a priority algorithm nicely captures the idea of a "greedy-like" type algorithm. While priority algorithms are applicable to many optimization problems, in this paper we consider the problem of makespan minimization in scheduling in the subset model. We show that by using a fixed priority algorithm one cannot achieve a considerable improvement over the approximation ratio given by the online greedy algorithm. Namely, we present an Ω(logm/loglogm) lower bound on the approximation ratio of any fixed priority algorithm where m is the number of machines.
AB - We continue the recent study of priority algorithms initiated by Borodin et al. [Proc. 13th ACM-SIAM Symp. on Discrete Algorithms, 2002, pp. 752-761]. The definition of a priority algorithm nicely captures the idea of a "greedy-like" type algorithm. While priority algorithms are applicable to many optimization problems, in this paper we consider the problem of makespan minimization in scheduling in the subset model. We show that by using a fixed priority algorithm one cannot achieve a considerable improvement over the approximation ratio given by the online greedy algorithm. Namely, we present an Ω(logm/loglogm) lower bound on the approximation ratio of any fixed priority algorithm where m is the number of machines.
KW - Approximation algorithms
KW - Scheduling
UR - http://www.scopus.com/inward/record.url?scp=0037110728&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0037110728&partnerID=8YFLogxK
U2 - 10.1016/S0020-0190(02)00264-8
DO - 10.1016/S0020-0190(02)00264-8
M3 - Article
AN - SCOPUS:0037110728
SN - 0020-0190
VL - 84
SP - 153
EP - 157
JO - Information Processing Letters
JF - Information Processing Letters
IS - 3
ER -