| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 431792 | Journal of Discrete Algorithms | 2006 | 14 Pages |
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|∑wiFiP|ri,pmtn|∑wiFi. 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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Luca Becchetti, Stefano Leonardi, Alberto Marchetti-Spaccamela, Kirk Pruhs,