All reports by Author Chandra Chekuri:

__
TR01-065
| 10th August 2001
__

Chandra Chekuri, Sanjeev Khanna#### Approximation Schemes for Preemptive Weighted Flow Time

Chandra Chekuri, Sanjeev Khanna

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