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

Distortion-Oblivious Algorithms for Minimizing Flow Time / Azar, Yossi; Leonardi, Stefano; Touitou, Noam. - (2022), pp. 252-274. [10.1137/1.9781611977073.13].

Distortion-Oblivious Algorithms for Minimizing Flow Time

Leonardi, Stefano
Co-primo
Membro del Collaboration Group
;
2022

Abstract

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 \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 Õ (μ), which is a quadratic improvement over the algorithm from STOC 2021, and is nearly optimal (we show a randomized lower bound of Ω(μ) on competitiveness).
2022
Proceedings of the 2022 {ACM-SIAM} Symposium on Discrete Algorithms, {SODA} 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022
978-1-61197-707-3
Scheduling Algorithms, Flow time Scheduling, Algorithms with prediction
02 Pubblicazione su volume::02a Capitolo o Articolo
Distortion-Oblivious Algorithms for Minimizing Flow Time / Azar, Yossi; Leonardi, Stefano; Touitou, Noam. - (2022), pp. 252-274. [10.1137/1.9781611977073.13].
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1685501
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 9
  • ???jsp.display-item.citation.isi??? ND
social impact