Download
Abstract:
We show that the Shortest Processing Time (SPT) algorithm is (Δ+1)/2-competitive for nonpreemptive uniprocessor total flow time, where Δ is the ratio between the longest and shortest job lengths. This is best possible for a deterministic algorithm and improves on the Δ+1 approximation ratio shown by Epstein and van Stee using different methods.
A preliminary version of this work is included in my master's thesis Approximating Total Flow Time, but that version contains a flawed proof and the presentation is substantially worse.