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
July 2003, 31 pages.
.
Status: available - back from printing
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.
-
- Attachement: MPI-I-2003-1-014.pdf (300 KBytes)
URL to this document: https://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},
}