2026-07-23T03:24:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9074 2024-03-06T10:43:18Z ddc:004 open_access

Non-Preemptive Flow-Time Minimization via Rejections Gupta, Anupam Kumar, Amit Li, Jason Scheduling Rejection Unrelated Machines Non-Preemptive 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 epsilon-fraction of the total weight of jobs, and compare the resulting flow-time to that of the offline 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Anupam Gupta and Amit Kumar and Jason Li 2018 Is Part Of LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2018.70 urn:nbn:de:0030-drops-90740 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.70 eng https://creativecommons.org/licenses/by/3.0/legalcode