Two Results on the List Update Problem

TitleTwo Results on the List Update Problem
Publication TypeTechnical Report
Year of Publication1990
AuthorsIrani S
Other Numbers601
KeywordsAmortized Analysis, Analysis of Algorithms, Competitive Analysis, Linear Lists, On-line Algorithms

In this paper we give a randomized on-line algorithm for the list update problem. Sleator and Tarjan show a deterministic algorithm, Move-to-Front, that achieves competitive ratio of (2L-1)/L for lists of length L. Karp an Raghavan show that no deterministic algorithm can beat 2L/(L+1). We show that Move-to-Front in fact achieves an optimal competitive ratio of 2L/(L+1). We show a randomized algorithm that achieves a competitive ratio of (31 L + 1 )/16(L+1) against an oblivious adversary. This is the first randomized strategy whose competitive factor beats a constant less than 2.

Bibliographic Notes

ICSI Technical Report TR-90-037

Abbreviated Authors

S. Irani

ICSI Publication Type

Technical Report