





















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 $\operatorname{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 \emph{distortion-oblivious} algorithms: algorithms which are competitive for \emph{every} input of \emph{every} distortion, and thus do not require knowledge of the distortion in advance. Moreover, the competitive ratios of our algorithms are $\tilde{O}(μ)$, which is a quadratic improvement over the algorithm from STOC 2021, and is nearly optimal (we show a randomized lower bound of $Ω(μ)$ on competitiveness).
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。