# MPI-I-2003-1-014

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

### SchÃ¤fer, Guido and Becchetti, Luca and Leonardi, Stefano and Marchetti-Spaccamela, Alberto and Vredeveld, Tjark

**MPI-I-2003-1-014**. July** **2003, 31 pages. | Status:** **available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:

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.

Acknowledgement:** **

References to related material:

To download this research report, please select the type of document that fits best your needs. | Attachement Size(s): |

| 300 KBytes |

Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView |

**URL to this document: **http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/2003-1-014

**BibTeX**
`@TECHREPORT{``SchÃ¤ferBecchettiLeonardiMarchetti-SpaccamelaVredeveld2003``,`

` AUTHOR = {Sch{\"a}fer, Guido and Becchetti, Luca and Leonardi, Stefano and Marchetti-Spaccamela, Alberto and Vredeveld, Tjark},`

` TITLE = {Average case and smoothed competitive analysis of the multi-level feedback algorithm},`

` TYPE = {Research Report},`

` INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},`

` ADDRESS = {Stuhlsatzenhausweg 85, 66123 Saarbr{\"u}cken, Germany},`

` NUMBER = {MPI-I-2003-1-014},`

` MONTH = {July},`

` YEAR = {2003},`

` ISSN = {0946-011X},`

`}`