On List Update and Work Function Algorithms(4)

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

4 that study could be helpful in the study of dynamic optimality for self-adjusting binary search tre

es 1], 15]. It is a long-standing open question whether or not there is a strongly competitive algorithm for dynamically rearranging a binary search tree using rotations, in response to a sequence of accesses. The similarity between Move-To-Front as an algorithm for dynamically rearranging linked lists, and the splay tree algorithm of Sleator and Tarjan 15] for dynamically rearranging binary search trees, long conjectured to be strongly competitive, is appealing. Our hope is that the use of work function-like algorithms might help to resolve this question for self-adjusting binary search trees.

1.3 ResultsThe main result of this paper is a proof that a class of work function algorithms is O(1) competitive for the list update problem.3 Proving this theorem requires getting a handle on the work function values, the optimal o ine costs of ending up in each state. This is tricky, as the o ine problem is very poorly understood. At present it is even unknown whether the problem of computing the optimal cost of executing a request sequence is NP-hard. The fastest optimal o -line algorithm currently known runs in time O(2k k!m), where k is the size of the list and m is the length of the request sequence 6]. Using the framework that we have developed for studying work functions and list update, we also present a new simple and illustrative proof that Move-ToFront and a large class of other online algorithms are (2? 1=k)-competitive. The rest of the paper is organized as follows. In Section 2, we present background material on work functions and on the work function algorithm. In Section 3, we present a formulation of the list update work functions in terms of a partial order on the elements of the list and use this formulation to prove that a large class of list update algorithms are (2? 1=k)-competitive. Finally, in Section 4 we present our main result, that work function algorithms are strongly competitive for list update.

2 BackgroundWe begin with background material on work functions and work function algorithms.

2.1 De nitionsConsider an arbitrary metrical task system, with states s 2 S and tasks 2 T . Given a sequence of requests, denote the t+ 1st request in the sequence as t+1 . Let t+1 be the task . Let (s) denote the cost of executing task in state s.3 The proof does not achieve the best possible competitive ratio of 2.