1 Search Results for "Schaefer, Guidouca"

Document
DOI: 10.4230/DagSemProc.05031.7
Average Case and Smoothed Competitive Analysis of the Multi-Level Feedback Algorithm

Authors: Luca Becchetti, Stefano Leonardi, Alberto Marchetti-Spaccamela, Guidouca Schaefer, and Tjark Vredeveld

Published in: Dagstuhl Seminar Proceedings, Volume 5031, Algorithms for Optimization with Incomplete Information (2005)

Abstract
In this paper we introduce the notion of smoothed competitive analysis of online algorithms. Smoothed analysis has been proposed by Spielman and Teng to explain the behaviour 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 Multi-Level Feedback (MLF) algorithm 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/\psigma)^3 + (2^k/\psigma)^2 2^{K-k}})$, where $\sigma$ 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, 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.
Cite as

Luca Becchetti, Stefano Leonardi, Alberto Marchetti-Spaccamela, Guidouca Schaefer, and Tjark Vredeveld. Average Case and Smoothed Competitive Analysis of the Multi-Level Feedback Algorithm. In Algorithms for Optimization with Incomplete Information. Dagstuhl Seminar Proceedings, Volume 5031, pp. 5-28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{becchetti_et_al:DagSemProc.05031.7,
  author =	{Becchetti, Luca and Leonardi, Stefano and Marchetti-Spaccamela, Alberto and Schaefer, Guidouca and Vredeveld, Tjark},
  title =	{{Average Case and Smoothed Competitive Analysis of the Multi-Level Feedback Algorithm}},
  booktitle =	{Algorithms for Optimization with Incomplete Information},
  pages =	{5--28},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5031},
  editor =	{Susanne Albers and Rolf H. M\"{o}hring and Georg Ch. Pflug and R\"{u}diger Schultz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05031.7},
  URN =		{urn:nbn:de:0030-drops-752},
  doi =		{10.4230/DagSemProc.05031.7},
  annote =	{Keywords: Competitive analysis , average case analysis , smoothed analysis , scheduling}
}
  • Refine by Author
  • 1 Becchetti, Luca
  • 1 Leonardi, Stefano
  • 1 Marchetti-Spaccamela, Alberto
  • 1 Schaefer, Guidouca
  • 1 Vredeveld, Tjark

  • Refine by Classification

  • Refine by Keyword
  • 1 Competitive analysis
  • 1 average case analysis
  • 1 scheduling
  • 1 smoothed analysis

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2005

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact