TY - GEN
T1 - Non-preemptive flow-time minimization via rejections
AU - Gupta, Anupam
AU - Kumar, Amit
AU - Li, Jason
N1 - Publisher Copyright:
© 2018 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.
PY - 2018/7/1
Y1 - 2018/7/1
N2 - We consider the online problem of minimizing weighted flow-time on unrelated machines. Although much is known about this problem in the resource-augmentation setting, these results assume that jobs can be preempted. We give the first constant-competitive algorithm for the non-preemptive setting in the rejection model. In this rejection model, we are allowed to reject an ε-fraction of the total weight of jobs, and compare the resulting flow-time to that of the o ine optimum which is required to schedule all jobs. This is arguably the weakest assumption in which such a result is known for weighted flow-time on unrelated machines. While our algorithms are simple, we need a delicate argument to bound the flow-time. Indeed, we use the dual-fitting framework, with considerable more machinery to certify that the cost of our algorithm is within a constant of the optimum while only a small fraction of the jobs are rejected.
AB - We consider the online problem of minimizing weighted flow-time on unrelated machines. Although much is known about this problem in the resource-augmentation setting, these results assume that jobs can be preempted. We give the first constant-competitive algorithm for the non-preemptive setting in the rejection model. In this rejection model, we are allowed to reject an ε-fraction of the total weight of jobs, and compare the resulting flow-time to that of the o ine optimum which is required to schedule all jobs. This is arguably the weakest assumption in which such a result is known for weighted flow-time on unrelated machines. While our algorithms are simple, we need a delicate argument to bound the flow-time. Indeed, we use the dual-fitting framework, with considerable more machinery to certify that the cost of our algorithm is within a constant of the optimum while only a small fraction of the jobs are rejected.
KW - Non-preemptive
KW - Rejection
KW - Scheduling
KW - Unrelated machines
UR - http://www.scopus.com/inward/record.url?scp=85049795194&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85049795194&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ICALP.2018.70
DO - 10.4230/LIPIcs.ICALP.2018.70
M3 - Conference contribution
AN - SCOPUS:85049795194
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018
A2 - Kaklamanis, Christos
A2 - Marx, Daniel
A2 - Chatzigiannakis, Ioannis
A2 - Sannella, Donald
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018
Y2 - 9 July 2018 through 13 July 2018
ER -