2026-07-23T05:05:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5634 2024-03-06T10:36:42Z ddc:004 open_access

Minimizing Weighted lp-Norm of Flow-Time in the Rejection Model Roy Choudhury, Anamitra Das, Syamantak Kumar, Amit online scheduling flow-time competitive analysis We consider the online scheduling problem to minimize the weighted ell_p-norm of flow-time of jobs. We study this problem under the rejection model introduced by Choudhury et al. (SODA 2015) - here the online algorithm is allowed to not serve an eps-fraction of the requests. We consider the restricted assignments setting where each job can go to a specified subset of machines. Our main result is an immediate dispatch non-migratory 1/eps^{O(1)}-competitive algorithm for this problem when one is allowed to reject at most eps-fraction of the total weight of jobs arriving. This is in contrast with the speed augmentation model under which no online algorithm for this problem can achieve a competitive ratio independent of p. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Anamitra Roy Choudhury and Syamantak Das and Amit Kumar 2015 Is Part Of LIPIcs, Volume 45, 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2015.25 urn:nbn:de:0030-drops-56341 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2015.25 eng https://creativecommons.org/licenses/by/3.0/legalcode