The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 28 NO.4 / (1999))
Approximability and Nonapproximability Results for Minimizing Total Flow Time on a Single Machine
Hans Kellerer, Thomas Tautenhahn, Gerhard J. Woeginger,
Pages. 1155-1166
Abstract We consider the problem of scheduling $n$ jobs that are released over time on a single
machine in order to minimize the total flow time. This problem is well known to be NP-complete,
and the best polynomial-time approximation algorithms constructed so far had (more or less trivial)
worst-case performance guarantees of $O(n)$.
indent In this paper, we present one positive and one negative result on polynomial-time approximations
for the minimum total flow time problem: The positive result is the first approximation algorithm
with a sublinear worst-case performance guarantee of $O(sqrt{n})$. This algorithm is based on resolving the
preemptions of the corresponding optimum preemptive schedule. The performance guarantee of our
approximation algorithm is not far from best possible, as our second, negative result demonstrates:
Unless $P=NP$, no polynomial-time approximation algorithm for minimum total flow time can have
a worst-case performance guarantee of $O(n^{1/2-varepsilon})$ for any $varepsilon > 0$.
Contents 1. Introduction
2. The approximation algorithm
2.1. How to handle small subtrees
2.2. How to handle the last root
2.3. How to handle fathers and sons
2.4. Putting everything together
3. The nonapproximability result
4. Concluding remarks
Key words scheduling, approximation algorithm, worst-case analysis, total flow time, release time, single machine
Mathmatical Subject Classification 08C85, 68Q20, 05C38, 68R10, 90