On List Update and Work Function Algorithms(9)

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

9 initial list is (a; b) and a b if the initial list is (b; a). Each successive request in results in a change of state in accordance with the transitions of the DFA, re ecting the work function

values after serving that request. Notice that the number of times a is referenced when in the state a b plus the number of times that b is referenced when in the state a b is equal to the total number of transitions into the middle DFA-state. The optimal sequence cannot avoid incurring cost upon such references. Therefore, the optimal cost of satisfying a sequence of requests is given by the number of transitions into the middle state of the DFA, plus the length of the sequence. The corresponding optimal o ine strategy is: Immediately before two or more references in a row to the same element, move that element to the front of the list. Now consider list update for a list of length k. The cost of an optimal sequence can be written as the sum of the number of exchanges performed 7 and the reference costs at each state. For any pair of elements (a; b) we can identify a pairwise reference cost attributable to (a; b), adding one whenever b is referenced but a is in front of b in the list, or vice versa. The standard list factoring approach is to describe the cost of any optimal sequence for satisfying by decomposing it into j j plus the sum over all pairs (a; b) of (i) this pairwise reference cost and (ii) all pairwise transpositions of a with b. For any pair (a; b), the sum of the pairwise transpositions and the pairwise reference cost describes a (possibly suboptimal) solution to the list of length two problem for the subsequence of consisting of references only to a and b. Therefore a lower bound on the optimal cost of satisfying is the sum of the costs of the optimal length-two solutions over all pairs (a; b), plus the length j j. It is important to note that this\list factoring" lower bound is not tight. Example 1. Consider a list of length ve, initialized abcde, and the reference sequence= ebddcceacde. The sum of the length-two solutions, plus the length of, is 31; the optimal cost of satisfying is 32. On the other hand, we do not know of any small examples where the optimal cost exceeds the list factoring lower bound by more than one, and we conjecture that the optimal cost does not exceed the lower bound by more than an additive constant related to the length of the list.

3.1 The partial order

We are thus led to consider the collection of k(k?1)=2 pairwise three-state DFAs, one for each pair a; b of elements in the list of length k. Consider the result of executing all these DFAs in parallel in response to requests in, starting from the states corresponding to the initial list. Figure 2 shows an example. Each DFA de nes a pairwise relation, a b, a b, or a b as the case may be, on the elements a and b. It is easy to verify that at every time t the resulting7 Recall that in our model we charge for each exchange, whether\paid" or\free"; each

free exchange in the standard model precisely corresponds in our model to a reduced reference cost on the immediately following reference. See 6], Theorem 1.