ALCOMFT-TR-03-110

Guido Schäfer and Naveen Sivadasan
Topology Matters: Smoothed Competitiveness of Metrical Task Systems
MPI. Work package 4. November 2003.

Abstract: We consider metrical task systems, a general framework to model a large class of online problems. Borodin, Linial and Saks gave a deterministic online algorithm, the work function algorithm (WFA), for metrical task systems. WFA has a competitive ratio of 2n-1, where n is the number of nodes in the underlying graph. In fact, the competitive ratio of WFA is optimal: Every deterministic online algorithm for metrical task systems must have a competitive ratio of at least 2n-1. Often, however, the competitive ratio is an over-pessimistic estimation of the performance of an online algorithm.

In this paper, we use the notion of smoothed competitiveness so as to capture the performance of WFA more adequately. We perturb, or smoothen, the request costs of a given task sequence by a probability distribution f and analyze the competitiveness of WFA on the perturbed sequence. Interstingly, our analysis reveals that the smoothed competitive ratio of WFA is much better and depends on several topological parameters of the underlying graph, such as the diameter, maximum degree, and minimum edge length.

Our analysis implies the following results for graphs with uniform edge lengths U, maximum degree D, and edge diameter diam.

(i) We provide the first average case analysis for WFA. We show that the expected competitive ratio of WFA is O(log(D)), if the request costs are chosen randomly from an arbitrary non-increasing distribution f with standard deviation \sigma = Theta(U).

(ii) We prove that the smoothed competitive ratio of WFA is O(diam(U/\sigma + log(D))) and O(\sqrt{n(U/\sigma + log(D))}), where \sigma denotes the standard deviation of the smoothing distribution. For example, already for perturbations with \sigma = Theta(U) the competitive ratio of WFA reduces to O(log(n)) on a clique and to O(\sqrt{n}) on a line. Our analysis holds for a large class of probability distributions, including the uniform and the normal distribution.

(iii) We present lower bounds on the smoothed competitive ratio of every deterministic algorithm showing that the above bounds are tight for a large class of graphs. We also give lower bounds for arbitrary graphs.

We also extend our results to graphs with arbitrary edge lengths: For a graph with diameter Diam and minimum edge length U_min, WFA has a smoothed competitive ratio of O(Diam/\sigma + (Diam/U_min)log(n)). This bound is tight up to a factor of at most log(n) for every deterministic algorithm.

Postscript file: ALCOMFT-TR-03-110.ps.gz (196 kb).