# Distortion-Oblivious Algorithms for Minimizing Flow Time

arXiv: https://arxiv.org/abs/2109.08424 · HTML: https://mlsanity.com/paper/2109.08424/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Sep 2021.

## Built on by (most cited first, 15 of 15)

- [Permutation Predictions for Non-Clairvoyant Scheduling](https://mlsanity.com/paper/2202.10199/) (2022)
- [Algorithms with Prediction Portfolios](https://mlsanity.com/paper/2210.12438/) (2022)
- [Online Scheduling for LLM Inference with KV Cache Constraints](https://mlsanity.com/paper/2502.07115/) (2025)
- [A Universal Error Measure for Input Predictions Applied to Online Graph Problems](https://mlsanity.com/paper/2205.12850/) (2022)
- [Sorting with Predictions](https://mlsanity.com/paper/2311.00749/) (2023)
- [Algorithms for Caching and MTS with reduced number of predictions](https://mlsanity.com/paper/2404.06280/) (2024)
- [Minimalistic Predictions to Schedule Jobs with Online Precedence Constraints](https://mlsanity.com/paper/2301.12863/) (2023)
- [Scheduling with Speed Predictions](https://mlsanity.com/paper/2205.01247/) (2022)
- [Speed-Oblivious Online Scheduling: Knowing (Precise) Speeds is not Necessary](https://mlsanity.com/paper/2302.00985/) (2023)
- [Queueing, Predictions, and LLMs: Challenges and Open Problems](https://mlsanity.com/paper/2503.07545/) (2025)
- [SkipPredict: When to Invest in Predictions for Scheduling](https://mlsanity.com/paper/2402.03564/) (2024)
- [Learning-Based Heavy Hitters and Flow Frequency Estimation in Streams](https://mlsanity.com/paper/2406.16270/) (2024)
- [Sorting and Hypergraph Orientation under Uncertainty with Predictions](https://mlsanity.com/paper/2305.09245/) (2023)
- [Learning-Augmented Algorithms: Guarantees, Construction Mechanisms, and System-Level Implications](https://mlsanity.com/paper/2609.04787/) (2026)
- [Robust Non-Clairvoyant Scheduling with Classification Models](https://mlsanity.com/paper/2610.01343/) (2026)

## Abstract (arXiv)

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 operatornameALGμ 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 tildeO(μ), which is a quadratic improvement over the algorithm from STOC 2021, and is nearly optimal (we show a randomized lower bound of Omega(μ) on competitiveness).