On the competitiveness of the move-to-front rule (Q1575556): Difference between revisions

We consider the list access problem and show that one questionable assumption in the original cost model presented by \textit{D. D. Sleator} and {R. E. Tarjan} [Amortized efficiency of list update and paging rules, Comm. ACM 28, No.~2, 202--208 (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\), MTF included.