On List Update and Work Function Algorithms(3)

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

3 One of the initial results about metrical task systems was that th

e work function algorithm (WFA) has competitive ratio 2n? 1 for all MTS's, where n is the number of states in the metrical task system 8]. It was also shown that this is best possible, in the sense that there exist metrical task systems for which no online algorithm can achieve a competitive ratio lower than 2n? 1. However, for many MTS's the upper bound of 2n? 1 is signi cantly higher than the best achievable competitive ratio. For example, there are known constant-competitive algorithms for list update, even though the MTS for a list of k elements has k! states. Another example is the k-server problem on a nite metric space?r consisting of r points. For this problem, the metrical task system has n= k states, but a celebrated result of Koutsoupias and Papadimitriou shows that in fact the very same work function algorithm is 2k? 1 competitive for this problem 12], nearly matching the known lower bound of k on the competitive ratio 13]. Unfortunately, our community understands very little at this point about how to design competitive algorithms that achieve close to the best possible competitive ratio for broad classes of metrical task systems. Indeed, one of the most intriguing open questions in this area is: For what metrical task systems is the work function algorithm strongly competitive? 2 Burley and Irani have shown the existence of metrical task systems for which the work function algorithm is not strongly competitive 14]. However, these\bad" metrical task systems seem to be rather contrived, and it is widely believed that the work function algorithm is in fact strongly competitive for large classes of natural metrical task systems. The desire to make progress towards answering this broad question is the foremost motivation for the work described in this paper. We were speci cally led to reconsider the list update problem when we observed the following curious fact: The Move-To-Front algorithm for list update is a work function algorithm. (Proposition 8, Section 4.) This observation was intriguing for two reasons. First because it raised the question of whether work function algorithms generally (that is, those with more general tie-breaking rules than that used in Move-To-Front ) are strongly competitive for list update. This would provide an example of a substantially di erent type of metrical task system for which the work function algorithm is strongly competitive than those considered in the past. The second and perhaps more exciting reason for studying work functions as they relate to list update is the tantalizing possibility that insight gained fromTheorem 1. We continue to use the term\paid exchanges" to describe speci cally those exchanges not involving the next-referenced element. 2 We say an algorithm is strongly competitive if its competitive ratio is within a constant factor of the best competitive ratio achievable.