Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR01-065 | 10th August 2001 00:00

Approximation Schemes for Preemptive Weighted Flow Time


Authors: Chandra Chekuri, Sanjeev Khanna
Publication: 26th September 2001 17:13
Downloads: 3196


We present the first approximation schemes for minimizing weighted flow time
on a single machine with preemption. Our first result is an algorithm that
computes a $(1+\eps)$-approximate solution for any instance of weighted flow
time in $O(n^{O(\ln W \ln P/\eps^3)})$ time; here $P$ is the ratio of
maximum job processing time to minimum job processing time, and $W$ is the
ratio of maximum job weight to minimum job weight. This result directly
gives a quasi-PTAS for weighted flow time when $P$ and $W$ are poly-bounded,
and a PTAS when they are both bounded. We strengthen the former result to
show that in order to get a quasi-PTAS it suffices to have just one of $P$
and $W$ to be poly-bounded. Our result provides a strong evidence that the
weighted flow time problem has a PTAS. We note that the problem is strongly
NP-hard even for bounded $P$ and $W$. We next consider two important
special cases of weighted flow time, namely, when $P$ is bounded and $W$ is
unrestricted, and when the weight of a job is inverse of its processing time
referred to as the stretch metric. For both cases we obtain a PTAS by
combining a novel partitioning scheme with our PTAS for the case of bounded
$P$ and $W$.

ISSN 1433-8092 | Imprint