In this paper we study some aspects of weighted flow time. We first show that the online algorithm Highest Density First is an O(1)-speed O(1)-approximation algorithm for P | ri, pmtn | ∑ wi Fi. We then consider a related Deadline Scheduling Problem that involves minimizing the weight of the jobs unfinished by some unknown deadline D on a uniprocessor. We show that any c-competitive online algorithm for weighted flow time must also be c-competitive for deadline scheduling. We then give an O(1)-competitive algorithm for deadline scheduling. © 2005 Elsevier B.V. All rights reserved.
Online weighted flow time and deadline scheduling / Becchetti, Luca; Leonardi, Stefano; MARCHETTI SPACCAMELA, Alberto; Kirk, Pruhs. - In: JOURNAL OF DISCRETE ALGORITHMS. - ISSN 1570-8667. - 4:3(2006), pp. 339-352. [10.1016/j.jda.2005.12.001]
Online weighted flow time and deadline scheduling
BECCHETTI, Luca;LEONARDI, Stefano;MARCHETTI SPACCAMELA, Alberto;
2006
Abstract
In this paper we study some aspects of weighted flow time. We first show that the online algorithm Highest Density First is an O(1)-speed O(1)-approximation algorithm for P | ri, pmtn | ∑ wi Fi. We then consider a related Deadline Scheduling Problem that involves minimizing the weight of the jobs unfinished by some unknown deadline D on a uniprocessor. We show that any c-competitive online algorithm for weighted flow time must also be c-competitive for deadline scheduling. We then give an O(1)-competitive algorithm for deadline scheduling. © 2005 Elsevier B.V. All rights reserved.| File | Dimensione | Formato | |
|---|---|---|---|
|
VE_2006_11573-237829.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
172.27 kB
Formato
Adobe PDF
|
172.27 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
