Topology matters: Smoothed competitiveness of metrical task systems

摘要

Borodin et al. (J. ACM 39 (1992) 745) introduced metrical task systems, a framework to model a large class of online problems. Metrical task systems can be described as follows. We are given a graph G = (V, E) with n nodes and a positive edge length (e) for every edge e G E. An online algorithm resides in G and has to service a sequence of tasks that arrive online. A task r specifies for each node nu is an element of V a request cost r (nu) E R-0(+) boolean OR {infinity}. If the algorithm resides in node u before the arrival of task tau, the cost to service task tau in node nu is equal to the shortest path distance from u to v plus the request cost r(v). The objective is to service all tasks at minimum total cost. Borodin et al. showed that every deterministic online algorithm has a competitive ratio of at least 2n - 1, independent of the underlying metric. Moreover, they presented an online work function algorithm (WFA) that achieves this competitive ratio.We present a smoothed competitive analysis of WTA. That is, given an adversarial task sequence, we randomly perturb the request costs and analyze the competitive ratio of WFA on the perturbed sequence. Here, we are mainly interested in the asymptotic behavior of WFA. 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 lambda(min), the maximum degree Delta, the edge diameter e(max), etc. For example, if the ratio between the maximum and the minimum edge length of G is bounded by a constant, the smoothed competitive ratio of WFA is O(e(max)(lambda(min)/sigma + log(Delta))) and O(root n (.) (lambda(min)/sigma + log(Delta))), where sigma denotes the standard deviation of the smoothing distribution. That is, already for perturbations with sigma = Theta(lambda(min)) the competitive ratio reduces to O(log(n)) on a clique and to O(root n) on a line. Furthermore, we provide lower bounds on the smoothed competitive ratio of any deterministic algorithm. We prove two general lower bounds that hold independently of the underlying metric. Moreover, we show that our upper bounds are asymptotically tight for a large class of graphs.We also provide the first average case analysis of WTA. We prove that WFA has O(log(Delta)) expected competitive ratio if the request costs are chosen randomly from an arbitrary non-increasing distribution with standard deviation sigma = Theta(lambda(min)). (c) 2005 Elsevier B.V. All rights reserved.