ECCC-Report TR01-065https://eccc.weizmann.ac.il/report/2001/065Comments and Revisions published for TR01-065en-usWed, 26 Sep 2001 17:13:57 +0200
Paper TR01-065
| Approximation Schemes for Preemptive Weighted Flow Time |
Chandra Chekuri,
Sanjeev Khanna
https://eccc.weizmann.ac.il/report/2001/065 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$.
Wed, 26 Sep 2001 17:13:57 +0200https://eccc.weizmann.ac.il/report/2001/065