Choudhury, Anamitra Roy ; Das, Syamantak ; Kumar, Amit (2015) Minimizing Weighted lp-Norm of Flow-Time in the Rejection Model In: 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015).
Full text not available from this repository.
Official URL: http://drops.dagstuhl.de/opus/volltexte/2015/5634
Abstract
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.
| Item Type: | Conference or Workshop Item (Paper) |
|---|---|
| Source: | Copyright of this article belongs to Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik. |
| ID Code: | 123517 |
| Deposited On: | 29 Sep 2021 09:41 |
| Last Modified: | 29 Sep 2021 09:41 |
Repository Staff Only: item control page
