On the competitiveness of the move-to-front rule (Q1575556)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: On the competitiveness of the move-to-front rule |
scientific article; zbMATH DE number 1493364
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On the competitiveness of the move-to-front rule |
scientific article; zbMATH DE number 1493364 |
Statements
On the competitiveness of the move-to-front rule (English)
0 references
21 August 2000
0 references
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.
0 references
competitive analysis
0 references
on-line algorithms
0 references
list update problem
0 references
move-to-front rule
0 references
