hide
Free keywords:
-
Abstract:
We consider online problems that can be modeled as \emph{metrical
task systems}:
An online algorithm resides in a graph $G$ of $n$ nodes and may move
in this graph at a cost equal to the distance.
The algorithm has to service a sequence of \emph{tasks} that arrive
online; each task specifies for each node a \emph{request cost} that
is incurred if the algorithm services the task in this particular node.
The objective is to minimize the total request cost plus the total
travel cost.
Several important online problems can be modeled as metrical task
systems.
Borodin, Linial and Saks \cite{BLS92} presented a deterministic
\emph{work function algorithm} (WFA) for metrical task systems
having a tight competitive ratio of $2n-1$.
However, the competitive ratio often is an over-pessimistic
estimation of the true performance of an online algorithm.
In this paper, we present a \emph{smoothed competitive analysis}
of WFA.
Given an adversarial task sequence, we smoothen the request costs
by means of a symmetric additive smoothing model and analyze the
competitive ratio of WFA on the smoothed task sequence.
Our analysis reveals that the smoothed competitive ratio of WFA
is much better than $O(n)$ and that it depends on several
topological parameters of the underlying graph $G$, such as
the minimum edge length $U_{\min}$, the maximum degree $D$,
and the edge diameter $diam$.
Assuming that the ratio between the maximum and the minimum edge length
of $G$ is bounded by a constant, the smoothed competitive ratio of WFA
becomes $O(diam (U_{\min}/\sigma + \log(D)))$ and
$O(\sqrt{n \cdot (U_{\min}/\sigma + \log(D))})$, where
$\sigma$ denotes the standard deviation of the smoothing distribution.
For example, already for perturbations with $\sigma = \Theta(U_{\min})$
the competitive ratio reduces to $O(\log n)$ on a clique and to
$O(\sqrt{n})$ on a line.
We also prove that for a large class of graphs these bounds are
asymptotically tight.
Furthermore, we provide two lower bounds for any arbitrary graph.
We obtain a better bound of
$O(\beta \cdot (U_{\min}/\psigma + \log(D)))$ on
the smoothed competitive ratio of WFA if each adversarial
task contains at most $\beta$ non-zero entries.
Our analysis holds for various probability distributions,
including the uniform and the normal distribution.
We also provide the first average case analysis of WFA.
We prove that WFA has $O(\log(D))$ expected competitive
ratio if the request costs are chosen randomly from an arbitrary
non-increasing distribution with standard deviation.
