MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

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
Conference URL::
http://theory.lcs.mit.edu/FOCS03/
Downloading URL:
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:
Note, Abstract, ©
(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},
 ADDRESS = {Cambridge, USA},
 MONTH = {October},
}

Entry last modified by Anja Becker, 06/17/2004
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Guido Schäfer		Created
01/08/2004 09:55:34
Revisions
5.
4.
3.
2.
1.		Editor(s)
Anja Becker
Anja Becker
Anja Becker
Christine Kiesel
Christine Kiesel		Edit Dates
17.06.2004 08:57:33
17.06.2004 08:55:57
17.06.2004 08:55:02
15.06.2004 14:21:48
01/08/2004 09:58:28 AM