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