Smoothed Competitiveness of Metrical Task Systems

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 tasks that arrive
online; each task specifies for each node a 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 presented a deterministic
Work Function Algorithm 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 talk, we present an Average Case/Smoothed
Competitive Analysis of the Work Function Algorithm.
If the request costs of the adversarial tasks are slightly
perturbed (smoothed) using some probability distribution, the
resulting competitive ratio is much better than 2n-1 depending
on the underlying graph parameters.
We also show lower bounds on the Smoothed Competitiveness.