Distortion-Oblivious Algorithms for Minimizing Flow Time

We consider the classic online problem of scheduling on a single machine to minimize total flow time. In STOC 2021, the concept of robustness to distortion in processing times was introduced: for every distortion factor μ, an O ( μ 2 )-competitive algorithm ALG μ which handles distortions up to μ was presented. However, using that result requires one to know the distortion of the input in advance, which is impractical. We present the first distortion-oblivious algorithms: algorithms which are competitive for every input of every distortion, and thus do not require knowledge of the distortion in advance. Moreover, the competitive ratios of our algorithms are Õ ( μ ), which is a quadratic improvement over the algorithm from STOC 2021, and is nearly optimal (we show a randomized lower bound of Ω( μ ) on competitiveness).

Authors

• Yossi Azar
• Stefano Leonardi 0001
• Noam Touitou

Keywords

No keywords are indexed for this paper.