On List Update and Work Function Algorithms

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

On List Update and Work Function AlgorithmsEric J. Anderson1, Kris Hildrum2, Anna R. Karlin1, April Rasala3, and Michael Saks41 Dept. of Computer Science, Univ. of Wash., feric,karling@cs.washington.edu 2 Computer Science Div., Univ. of Calif., Berkeley, hildrum@cs.berkeley.edu 3 Lab. of Computer Science, Mass. Inst. of Tech., arasala@theory.lcs.mit.edu 4 Dept. of Mathematics, Rutgers Univ., saks@math.rutgers.edu

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 constant competitive ratio for list update. In the process, we present a new formulation of the well-known\list factoring" technique in terms of a partial order on the elements of the list. This approach leads to a new simple proof that a large class of online algorithms, including Move-To-Front, is (2? 1=k)-competitive.

1 IntroductionThe list accessing or list update problem is one of the most well-studied problems in competitive analysis 1], 2], 3], 4], 5]. The problem consists of maintaining a set S of items in an unsorted linked list, for example as a data structure for implementation of a dictionary. The data structure must support three types of requests: ACCESS(x), INSERT(x) and DELETE(x), where x is the name, or\key", of an item stored in the list. We associate a cost with each of these operations as follows: accessing or deleting the i-th item on the list costs i; inserting a new item costs j+ 1 where j is the number of items currently on the list before insertion. We also allow the list to be reorganized, at a cost measured in terms of the minimum number of transpositions of consecutive items needed for the reorganization. We consider the standard cost model in the literature: immediately after an access or an insertion, the requested item may be moved at no extra cost to a position closer to the front of the list. These exchanges are called free exchanges. Intuitively, using free exchanges, the algorithm can lower the cost on subsequent requests. In addition, at any time, two adjacent items in the list can be exchanged at a cost of 1. These exchanges are called paid exchanges. The list update problem is to devise an algorithm for reorganizing the list, by performing free and/or paid exchanges, that minimizes search and reorganization costs. As usual, the algorithm will be evaluated in terms of its competitive ratio. As with much of the work on list accessing, we will focus on the static list update problem, where the list starts out with k elements in it, and all requests are

1.1 Motivation