On List Update and Work Function Algorithms(14)

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

14

4.2 WFA is O(1) competitive for list update.0

In the preceding section, we characterized the work function algorithm in terms of the work function values of states formed by moving the referenced element forward. We noted that the work function value cannot increase as the referenced element is moved forward. In order to prove results about the work function algorithm, however, we must characterize all states to which the work function algorithm could move; and thus we must characterize circumstances under which the work function value must strictly decrease. Our proof technique, then, supposes by hypothesis that the work function algorithm encounters a state of a particular undesired type; we consider the optimal sequence of interchanges and references that leads to the given work function value; then we must construct a new sequence, leading to a state identical to the rst but for moving the referenced element forward, for which the total cost (of references and interchanges) is strictly lower. The technically challenging part of the proof is the following lemma.

Lemma 2. Consider= 1; x; 2; x, where in 2 there are no references to x, and j j= t. Let S be any fundamental state at the nal time step t. Let N be the set of elements that are not referenced in 2 that are in front of x in S, and let R be the set of elements (not including x) that are referenced^ in 2 . Also, let S be S with x m

oved forward just in front of the element in Nclosest to the front of the list. Then^ !t (S ) !t (S )+ jRj? jNj:

(3)

Proof. Suppose O is an optimal sequence ending in S after satisfying 1; x; 2; x, so that the cost of O is the work function value !t(S ). Let T denote the state in which O satis es the penultimate reference to x (between 1 and 2 ). We note that, at the point immediately prior to the penultimate reference to x (at time k, say), the cost of O is !k?1 (T ). In this construction, we modify O between T^^^ and S so as to obtain the state S, with S"x S and !t (S ) !t (S )? jNj+ jRj. Let N denote the total number of elements not referenced between k= x and t= x. (This set speci cally includes x, and is potentially much larger than jNj, which is the number of such elements in front of x in S .) Label these nonreferenced elements p1;:::; pN in the order they occur in the state T, with p1 referring to the one such closest to the front of the list. Denote by I X; Y] the number of interchanges of non-referenced elements (other than x) in a given sequence between the states X and Y .^ The construction of the lower-cost state S proceeds in three stages (see below for a diagram): 1. Rearrange the respective order of the non-referenced elements within T to obtain some state T 0. In T 0, x will occupy the location of the front-most nonreferenced element in T . All other non-referenced elements p in T 0 will satisfy a non-decreasing depth property, that p(T ) p(T 0).9 All referenced elements 9 Recall that we denote the depth of an element p in the state X by p(X ).