TR01-065 Authors: Chandra Chekuri, Sanjeev Khanna

Publication: 26th September 2001 17:13

Downloads: 3293

Keywords:

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$.