Abstract. The list update problem, a well-studied problem in dynamic data structures, can be described abstractly as a metrical task system. In this paper, we prove that a generic metrical task system algorithm, called the work function algorithm, has cons

2 accesses. The results described are easily extended to the dynamic case including insertions and deletions. Speci cally, the cost of an insertion is the same for any algorithm; and the cost of a deletion is the same as the cost of an access. Some results for static list update

are expressed in terms of the length k of the list. In the case of dynamic list update, the length k is no longer uniquely de ned. However, for constant-competitive ratio results, it is enough for our purposes to interpret k as the maximum length of the list where necessary. Many deterministic online algorithms have been proposed for the list update problem. Of these, perhaps the most well-known is the Move-To-Front algorithm: after accessing an item, move it to the front of the list, without changing 2 the relative order of the other items. Move-To-Front is known to be 2? k+1 competitive, and this is best possible 2], 7]. We note that other cost models have also been considered for the list update problem 6], 9], 10]. Increasing the cost of exchanges to two (instead of one) makes Move-To-Front optimal; this provides an independent proof that MoveTo-Front is two-competitive. Other alternatives analyzed in the literature include allowing free exchanges for other than the referenced element, and allowing free exchanges between elements that are not adjacent 9], 10]. These alternative cost models can lead to qualitatively di erent results.

1.2 Metrical task systemsThe (static) list update problem can also be considered within the metrical task system framework introduced by Borodin, Linial and Saks 8]. Metrical task systems (MTS) are an abstract model for online computation that captures a wide variety of online problems (paging, list update and the k-server problem, to name a few) as special cases. A metrical task system is a system with n states, with a distance function d de ned on the states: d(i; j ) is the distance between states i and j . The distances are assumed to form a metric. The MTS has a set T of allowable tasks; with each task 2 T is associated a vector ( (1); (2);:::; (n)) where (i) is the (nonnegative) cost of processing task in state i. An online algorithm is given a starting state and a sequence of tasks to be processed online, and must decide in which state to process each task. The goal of the algorithm is to minimize the total distance moved plus the total processing costs. The list update problem can be viewed as a metrical task system as follows. The states of the list update MTS are the k! possible orderings of the k elements in the list, which we also call list con gurations. There are k possible tasks, one corresponding to each list element x. The cost x ( ) of processing the task x in a particular list con guration, is equal to the depth of x in the list . The distance between two states or list con gurations is the number of inversions between the list orderings, considered as permutations.11 In this formulation,\free exchanges" are treated as made at unit cost immediately

before the item is referenced. Because the cost of these exchanges is precisely o set by the lower reference cost, this model is identical to the standard model. See 6],