On the competitiveness of the move-to-front rule

We consider the list access problem and show that one questionable assumption in the original cost model presented by Sleator and Tarjan (1985) and subsequent literature allowed for several competitiveness; results of the move-to-front rule (MTF). We present an off-line algorithm for the list access problem and prove that, under a. more realistic cost model, no on-line algorithm can be c-competitive for any constant c, MTT: included. (C) 2000 Elsevier Science B.V. All rights reserved.