In this paper, we introduce the notion of smoothed competitive analysis of online algorithms. Smoothed analysis has been proposed by Spielman and Teng [25] to explain the behavior of algorithms that work well in practice while performing very poorly from a worst-case analysis point of view. We apply this notion to analyze the multilevel feedback algorithm (MLF) to minimize the total flow time on a sequence of jobs released over time when the processing time of a job is only known at time of completion. The initial processing times are integers in the range [1, 2(k)]. We use a partial bit randomization model, i.e., the initial processing times are smoothed by changing the k least significant bits under a quite general class of probability distributions. We show that MLF admits a smoothed competitive ratio of O((2(k)/sigma)(3) +(2(k)/sigma)(2)2(K-k)), where or denotes the standard deviation of the distribution. In particular. we obtain a competitive ratio of O(2(K-k)) if sigma = Theta(2(k)). We also prove an Omega(2(K-k)) lower bound for any deterministic algorithm that is run on processing times smoothed according to the partial bit randomization model. For various other smoothing models, including the additive symmetric smoothing one, which is a variant of the model used by Spielman and Teng [25], we give a higher lower bound of Omega(2(K)). A direct consequence of our result is also the first average-case analysis of MLF. We show a constant expected ratio of the total flow time of MLF to the optimum under several distributions including the uniform one.

Average-case and smoothed competitive analysis of the multilevel feedback algorithm / Becchetti, Luca; Leonardi, Stefano; MARCHETTI SPACCAMELA, Alberto; G., Schaefer; Tjark, Vredeveld. - In: MATHEMATICS OF OPERATIONS RESEARCH. - ISSN 0364-765X. - 31:1(2006), pp. 85-108. [10.1287/moor.1050.0170]

Average-case and smoothed competitive analysis of the multilevel feedback algorithm

BECCHETTI, Luca;LEONARDI, Stefano;MARCHETTI SPACCAMELA, Alberto;
2006

Abstract

In this paper, we introduce the notion of smoothed competitive analysis of online algorithms. Smoothed analysis has been proposed by Spielman and Teng [25] to explain the behavior of algorithms that work well in practice while performing very poorly from a worst-case analysis point of view. We apply this notion to analyze the multilevel feedback algorithm (MLF) to minimize the total flow time on a sequence of jobs released over time when the processing time of a job is only known at time of completion. The initial processing times are integers in the range [1, 2(k)]. We use a partial bit randomization model, i.e., the initial processing times are smoothed by changing the k least significant bits under a quite general class of probability distributions. We show that MLF admits a smoothed competitive ratio of O((2(k)/sigma)(3) +(2(k)/sigma)(2)2(K-k)), where or denotes the standard deviation of the distribution. In particular. we obtain a competitive ratio of O(2(K-k)) if sigma = Theta(2(k)). We also prove an Omega(2(K-k)) lower bound for any deterministic algorithm that is run on processing times smoothed according to the partial bit randomization model. For various other smoothing models, including the additive symmetric smoothing one, which is a variant of the model used by Spielman and Teng [25], we give a higher lower bound of Omega(2(K)). A direct consequence of our result is also the first average-case analysis of MLF. We show a constant expected ratio of the total flow time of MLF to the optimum under several distributions including the uniform one.
2006
average-case analysis; competitive analysis; multilevel feedback; scheduling
01 Pubblicazione su rivista::01a Articolo in rivista
Average-case and smoothed competitive analysis of the multilevel feedback algorithm / Becchetti, Luca; Leonardi, Stefano; MARCHETTI SPACCAMELA, Alberto; G., Schaefer; Tjark, Vredeveld. - In: MATHEMATICS OF OPERATIONS RESEARCH. - ISSN 0364-765X. - 31:1(2006), pp. 85-108. [10.1287/moor.1050.0170]
File allegati a questo prodotto
File Dimensione Formato  
VE_2006_11573-235526.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 531.29 kB
Formato Adobe PDF
531.29 kB Adobe PDF   Contatta l'autore

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/235526
 Attenzione

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

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