On List Update and Work Function Algorithms(5)

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

5

De nition 1. The work function !t(s) for any state s and index t is the lowest

cost of satisfying the rst t requests of and ending up in state s 16], 8]. Because the states and task costs are time-independent, the work functions can be calculated through a dynamic programming formulation (which can equally be taken as the de nition): !t+1(s0 )= min (!t (s)+ (s)+ d(s; s0 )): (1) s

The work function algorithm is de ned in terms of fundamental states: De nition 2. A state f is fundamental at time t if it satis es !t+1(f )= !t (f )+ (f ): (Where the context is evident, we will simply say a state f is\fundamen

tal".) The Work Function Algorithm (WFA), 16], 8], de ned for an arbitrary metrical task system, is the following: De nition 3. WFA: When in state st, service the request t+1= in the state st+1 such that st+1= argmins (!t+1 (s)+ d(st; s)) where the minimum is taken over states s that are fundamental at time t. From De nition 1, we see that the work function algorithm chooses st+1 so that st+1= argmins (!t (s)+ (s)+ d(st; s)): (2) We consider a variant of this work function algorithm, di ering only in the subscript of the work function: De nition 4. WFA0: When in state st, service the request in the state st+1 such that st+1= argmins (!t+1 (s)+ (s)+ d(st; s)): The minimum in this expression may not be unique. Accordingly, we de ne the class of states to which the work function algorithm might move: De nition 5. Given that WFA0 visits state st at time t, a state s at time t+ 1 is wfa-eligible if it is one of the states that minimizes the expression in De nition 4. We will see that, when applying WFA0 to list update, there always exists at least one wfa-eligible state that requires no paid exchanges (Proposition 8). In the remainder of the paper, we will assume that WFA0 chooses to move to a wfaeligible state of this type, i.e., one that can be reached by moving the referenced element only. We next note several elementary identities, which hold at all times t and all states s and s0 . As above, we let denote the t+ 1st task, and (s) its task cost in the state s.