max planck institut

informatik

informatik

**MPI-I-2003-1-016**. December** **2003, 28 pages. | Status:** **available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:

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.

Acknowledgement:** **

References to related material:

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

444 KBytes | |

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