On List Update and Work Function Algorithms(20)

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

20 between it and qj?1, and q1 with all referenced elements between it and x. Each referenced element between x and qi?1 interchanges with at most one nonreferenced element, and each such is in front of x in S . Thus the number of^ exchanges required to transform S 0 to S, plus the number of referenced elements 0, plus the number of non-referenced elements in front of x in in front of x in S S, is no greater than the depth of x in S . The result follows. t u Finally, we address the most intricate part of the construction: Proposition 11. Suppose S 0 is derived from S, such that (i) all referenced elements p have p(S 0 )= p(S ), (ii) x occupies in S 0 the position of the front-most non-referenced element in S, and (iii) all other non-referenced elements are in their same respective order in S 0 as in S . Then there is a T 0 with the nondecreasing depth property, and a subsequence O0 O, such that (i) O0 (T 0)= S 0, and (ii) the cost of O is at least the cost of O0 plus the cost of interchanges I T 0; T] of non-referenced elements (other than x) necessary to derive T 0 from T. Proof. As above, we denote by pi the non-referenced element occupying the i0 th non-referenced position in T . For convenience, let z denote the location of x as a non-referenced element in T, pz= x.11 We proceed by iteratively constructing T 0 from the end of the list, beginning with O?1 (S 0 ). The location of referenced elements remains xed throughout the construction. As a result, we consider only the N positions of non-referenced elements. For convenience, we describe the iteration as proceeding from i= N to i= 1. (The\base case" is denoted by\i= N+ 1".) At each step, then, we de ne a map Oi: Ti0 ! S 0 . The non-decreasing depth property is maintained for the elements (other than x) in Oi?1 (S 0 )= Ti0 that occupy the locations i through N in Ti0. We show that any necessary interchanges of elements as we proceed from Ti0 to Ti0?1 correspond to transpositions in Oi0 . For each pair of elements p; q 6= x at locations i and below in Ti0, we can determine whether these two elements are in the same or in the opposite order in T . We denote by Ii Ti0; T] the number of pairwise inversions of such elements (other than x). We denote by jOj (respectively, jOi j) the number of transpositions in the sequence O (respectively, Oi ). Formally, we show by induction that for each i: 1. Oi (Ti0 )= S 0 (and Oi?1: S 0 ! Ti0 ) 2. Oi O in the sense of a subsequence of transpositions, and jOj jOi j+ Ii Ti0; T] (all swaps and inversions are accounted for) 3. x(Ti0 ) pi (T ) (x is no deeper than position i) 4. 8p 6= x with p(T ) pi (T ); p(Ti0) p(T ) (all elements other than x at position i or below in T have the non-decreasing depth property) 5. 8p; q 6= x with p(T ); q(T )< pi (T )

: (a) p(S )< x(S ) () p(Ti0) 6= p(T ), and p(S )> x(S ) () p(Ti0)= p(T )positions of non-referenced elements in T .

11 We use the terms\position" and\location" interchangeably to refer to the respective