English

# Item

ITEM ACTIONSEXPORT
Average case and smoothed competitive analysis of the multi-level feedback algorithm

Schäfer, G., Becchetti, L., Leonardi, S., Marchetti-Spaccamela, A., & Vredeveld, T.(2003). Average case and smoothed competitive analysis of the multi-level feedback algorithm (MPI-I-2003-1-014). Saarbrücken: Max-Planck-Institut für Informatik.

Item is

show hide
Genre: Report

### Files

show Files
hide Files
:
2003-1-014 (Any fulltext), 12KB
Name:
2003-1-014
Description:
-
Visibility:
Public
MIME-Type / Checksum:
text/html / [MD5]
-
-
-

show

### Creators

show
hide
Creators:
Schäfer, Guido1, Author
Becchetti, Luca2, Author
Leonardi, Stefano1, Author
Marchetti-Spaccamela, Alberto2, Author
Vredeveld, Tjark2, Author
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019
2External Organizations, ou_persistent22

### Content

show
hide
Free keywords: -
Abstract: In this paper we introduce the notion of smoothed competitive analysis of online algorithms. Smoothed analysis has been proposed by Spielman and Teng [\emph{Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time}, STOC, 2001] 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, 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.

### Details

show
hide
Language(s): eng - English
Dates: 2003
Publication Status: Published in print
Pages: 31 p.
Publishing info: Saarbrücken : Max-Planck-Institut für Informatik
Rev. Type: -
Identifiers: URI: http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/2003-1-014
Report Nr.: MPI-I-2003-1-014
Degree: -

show

show

show

### Source 1

show
hide
Title: Research Report / Max-Planck-Institut für Informatik
Source Genre: Series
Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: - Identifier: -