Approximation schemes for preemptive weighted flow time

Chandra Chekuri, Sanjeev Khanna

Research output: Contribution to journalConference articlepeer-review

Abstract

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 + ε)-approximate solution for any instance of weighted flow time in O(nO(In W In P/ε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 O(1). 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 strong evidence to the hypothesis that the weighted flow time problem has a PTAS. We note that the problem is strongly NP-hard even when P and W are O(1). We next consider two important special cases of weighted flow time, namely, when P is O(1) and W is arbitrary, and when the weight of a job is inverse of its processing time referred to as the stretch metric. For both of the above special cases we obtain a (1 + ε)-approximation for any ε > 0 by using a randomized partitioning scheme to reduce an arbitrary instance to several instances all of which have P and W bounded by a constant that depends only on ε.

Original languageEnglish (US)
Pages (from-to)297-305
Number of pages9
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
DOIs
StatePublished - 2002
Externally publishedYes
EventProceedings of the 34th Annual ACM Symposium on Theory of Computing - Montreal, Que., Canada
Duration: May 19 2002May 21 2002

ASJC Scopus subject areas

  • Software

Cite this