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

11Proof. Any online algorithm A that maintains a list order consistent with the partial order and performs no paid exchanges has a total cost A( ) satisfying P A( ) n+ t (It+ Gt ), where j j= n. ByP Lemma 1 and the fact that OPT ( ) kn, we can conclude that A( ) t u n+ 2 t Gt (2? 1=k)OPT ( ):

3.2 Competitive analysis of online algorithmsTheorem 1 provides a new, simple proof that a collection of online algorithms (many already known to be com

petitive) are all 2? 1=k competitive. These algorithms include Move-To-Front, TimeStamp, MRI (k), and SBR( ) 4], 5], 11]. Each of these online algorithms moves only the referenced element. By Theorem 1, it is enough to show that these algorithms maintain lists consistent with the partial order. We observed above that Move-To-Front maintains lists consistent with the partial order. Suppose the list is consistent with the partial order at time t, immediately before a reference to x. Then immediately after the reference (and after x is moved to the front), each element of the list is less than or incomparable to x, and is also behind x in the list. And because the respective pairwise order of other elements does not change, the list remains consistent with the partial order at time t+ 1. The TimeStamp algorithm (originally called TimeStamp (0)) due to Albers 4] is de ned as follows: On a request for an item x, insert x in front of the rst (from the front of the list) item y that precedes x on the list and was requested at most once since the last request for x. Do nothing if there is no such item y or if x is being requested for the rst time. The TimeStamp algorithm makes only free exchanges. Furthermore, by construction, after a reference to x, each item y that precedes it in the resulting list must have been requested at least twice since the last request for x. Therefore every element in front of x is incomparable to x (and not less than x) after the request. Each element behind x is less than or incomparable to x. Finally, the respective orders of other elements do not change as a result of the reference to x. Immediately prior to the initial reference to x, all elements in front of it are greater than it in the partial order. Hence TimeStamp{ and indeed any algorithm that moves x forward at least as far as TimeStamp does{ maintains a list order consistent with the partial order. Ran El-Yaniv has recently presented another family of algorithms, the MRI (k) family 5]: On a request for an item x, move x forward to just behind the rearmost item y that precedes x on the list and was requested at least k+ 1 times since the last request for x. If there is no such item y or if x is being requested for the rst time, move x to the front.