An Optimal Online Algorithm for Robust Flow Time Scheduling
Gupta, A; Kumar, A; Panigrahi, D; Wang, Z
Published in: Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms
The problem of minimizing the total flow time on a single machine is one of the few problems for which we can give an optimal online algorithm: just schedule the job with the shortest remaining processing time (SRPT). However, this requires knowledge of the true running time pj of each job j. Azar, Leonardi, and Touitou recently asked: what if we are given estimates p̂j for each job, such that the multiplicative error between pj and p̂j (called the distortion) is at most µ? It is easy to construct examples where no algorithm can be o(µ) competitive; can we get O(µ) competitiveness? We show how to achieve this asymptotically optimal result, improving on the previous best result of O(µ log µ). Moreover, we give a very simple algorithm to get this tight bound of O(µ); the previous ZigZag algorithm was relatively more involved. Our proof is via a dual-fitting argument based on the idea of a reduced instance: we consider an LP relaxation based on knapsack-cover inequalities, and show a solution with a large dual value. Our ideas can also be extended to give alternative dual-fitting arguments for previously analyzed algorithms (like SRPT, ZigZag, and others for minimizing the total flow time, and the Bansal-Dhamdhere algorithm for weighted flow-time minimization).
