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
\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.
