Proceedings Article, Paper @InProceedings Beitrag in Tagungsband, Workshop

 Show entries of: this year (2020) | last year (2019) | two years ago (2018) | Notes URL
 Action: login to update Options: Goto entry point

 Author, Editor
 Author(s): Becchetti, Luca Leonardi, Stefano Marchetti-Spaccamela, Alberto Schäfer, Guido Vredeveld, Tjark dblp dblp dblp dblp dblp Not MPG Author(s): Becchetti, Luca Leonardi, Stefano Marchetti-Spaccamela, Alberto Vredeveld, Tjark
 Editor(s):
 BibTeX cite key*: Schäfer2003

 Title, Booktitle
 Title*: Average Case and Smoothed Competitive Analysis of the Multi-Level Feedback Algorithm Booktitle*: 44th Annual Symposium on Foundations of Computer Science (FOCS-03)

 Event, URLs
 URL of the conference: http://theory.lcs.mit.edu/FOCS03/ URL for downloading the paper: http://www.mpi-sb.mpg.de/~schaefer/ftp/ps/sa-mlf.ps.gz Event Address*: Cambridge, USA Language: English Event Date* (no longer used): 11-14 October 2003 Organization: IEEE Computer Society Technical Committee on Mathematical Foundations of Computing Event Start Date: 11 October 2003 Event End Date: 14 October 2004

 Publisher
 Name*: IEEE URL: http://www.computer.org/ Address*: New York, USA Type:

 Vol, No, Year, pp.
 Series:
 Volume: Number: Month: October Pages: 462-471 Year*: 2003 VG Wort Pages: ISBN/ISSN: Sequence Number: DOI:

 (LaTeX) Abstract: In this paper we introduce the notion of smoothed competitive analysis of online algorithms. Smoothed analysis has been proposed by Spielman and Teng \cite{ST01} 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, where the initial processing times are smoothened 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 $\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 smoothened according to the partial bit randomization model. For various other smoothening models, including the additive symmetric smoothening model used by Spielman and Teng \cite{ST01}, 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 distribution. Download Access Level: Public

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group External Affiliations: Dipartimento di Informatica e Sistemistica, Universita di Roma La Sapienza'', Italy Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@INPROCEEDINGS{Schäfer2003,
AUTHOR = {Becchetti, Luca and Leonardi, Stefano and Marchetti-Spaccamela, Alberto and Sch{\"a}fer, Guido and Vredeveld, Tjark},
TITLE = {Average Case and Smoothed Competitive Analysis of the Multi-Level Feedback Algorithm},
BOOKTITLE = {44th Annual Symposium on Foundations of Computer Science (FOCS-03)},
PUBLISHER = {IEEE},
YEAR = {2003},
ORGANIZATION = {IEEE Computer Society Technical Committee on Mathematical Foundations of Computing},
PAGES = {462--471},