Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > WEIGHTED FLOW TIME:
Reports tagged with weighted flow time:
TR01-065 | 10th August 2001
Chandra Chekuri, Sanjeev Khanna

#### Approximation Schemes for Preemptive Weighted Flow Time

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

ISSN 1433-8092 | Imprint