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 $p_j$ of each job~$j$. Azar, Leonardi, and Touitou recently asked: what if we are given estimates $\hatp_j$ for each job, such that the multiplicative error between $p_j$ and $\hatp_j$ (called the \emph{distortion}) is at most $\mu$? It is easy to cnstruct examples where no algorithm can be $o(\mu)$ competitive; can we get $O(\mu)$ competitiveness?

 

We show how to achieve this asymptotically optimal result, improving on the previous best result of $O(\mu \log \mu)$. Moreover, we give a very simple algorithm to get this tight bound of $O(\mu)$; the previous ZigZag algorithm was relatively more involved. Our proof is via a dual-fitting argument based on the idea of a \emph{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).

Zhaozi Wang is a second-year Ph.D. student at the Courant Institute School of Mathematics, Computing, and Data Science, where he is fortunate to be advised by Prof. Anupam Gupta. Previously, he obtained a bachelor’s degree in Computer Science from Shanghai Jiao Tong University, ACM class. His research interests lie in online algorithms, scheduling, and graph algorithms.