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

10

x1

? x2? x3

x3

x1

x3?

-

? x2

x2

x2

x1?

-

? x3

x3

x3

x2

x2 x2

-

? x1

?

-

? x3? x1

Fig. 2. Illustration of the evolution of the partial order on three elements in response

to the request sequence= x3; x2; x3; x2 assuming the initial list is ordered x1; x2; x3 from front to back. As usual, a directed edge from a to b indicates that a b in the partial order, whereas the absence of an edge indicates that a b

collection of relations de nes a valid partial order on the k elements of the list. In particular, the list con guration obtained by following Move-To-Front at every step is always consistent with this partial order. This partial order at each time t is de ned by the reference sequence, and does not depend on any choice of algorithm for list update. When we refer to the\partial order", we mean this partial order as induced by a particular at a given time t. When we say that an algorithm is\consistent with the partial order", we mean that, when applied to a reference sequence, the list con guration visited by the algorithm at each time t, considered as a total order of the list elements, is consistent with the partial order induced by at that time t. De ne by Gt (respectively It ) the number of elements greater than (respectively incomparable to) t in this partial order immediately prior to its reference at time t. By the discussion above, the optimal cost of servicing a request sequence of length n and ending up in any state s is bounded below by the number of transitions into middle states of the DFAs, which at each step t is Gt . P Hence for states s, !n (s) n+ 1 t n Gt: An easy counting argument also shows: Lemma 1. Pt It Pt Gt .Proof. Since we start with a total ordering on the elements, determined by the initial ordering of the list, each two element DFA begins either in state a b or a b. For each DFA, each transition out of its middle state a b must therefore be preceded by a transition into the middle state. Taken together, this implies that, cumulatively, the number of transitions out of middle states P cannot exceed the number of transitions into middle states. Since Gt is the P cumulative number of transitions into middle states of the DFA's, and It the cumulative number of transitions out of middle states, the result follows. t u

Lemma 1 leads to a useful characterization of online algorithms: Theorem 1. Any online list update algorithm that performs only free exchanges and maintains the invariant that the list order is consistent with the partial order is (2? 1=k)-competitive.