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