An Optimal Online Algorithm for Robust Flow Time Scheduling

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 $\hat{p}_j$ for each job, such that the multiplicative error between $p_j$ and $\hat{p}_j$ (called the distortion) is at most $\mu$? It is easy to construct examples where no algorithm can be $o(\mu)$ competitive; can we get $O(\mu)$ competitiveness?