Computer Science Department
School of Computer Science, Carnegie Mellon University
Minimizing Weighted Flow Time
Nikhil Bansal, Kedar Dhamdhere
April 2002
CMU-CS-02-128.ps
CMU-CS-02-128.pdf
We consider the problem of minimizing weighted flow time on
a single machine in the preemptive setting. Our first result is an
online algorithm which achieves a competitive ratio of k if
there are k weight classes. Even for the special case of
k=2 this gives the first O(1)-competitive
algorithm. Our algorithm also directly gives an O(log{W})
competitive algorithm when the maximum to the minimum ratio of
weights is W. Our second result deals with
the non-clairvoyant setting where the job sizes are unknown (but the weight
of the jobs are known). In this case, we give a resource augmented
algorithm. In particular, if the non-clairvoyant online algorithm is
allowed a (1+epsilon) speed-up, then it is (1+1/epsilon) competitive
against an optimal offline, clairvoyant algorithm.
20 pages
Return to:
SCS Technical Report Collection This page maintained by [email protected]
School of Computer Science homepage