Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








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:




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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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 AM
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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section