Publication Details
Title: Two Results on the List Update Problem
Author: S. Irani
Group: ICSI Technical Reports
Date: August 1990
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-90-037.pdf
Overview:
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. Keywords: Analysis of Algorithms, On-line Algorithms, Competitive Analysis, Amortized Analysis, Linear Lists.
Bibliographic Information:
ICSI Technical Report TR-90-037
Bibliographic Reference:
S. Irani. Two Results on the List Update Problem. ICSI Technical Report TR-90-037, August 1990
Author: S. Irani
Group: ICSI Technical Reports
Date: August 1990
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-90-037.pdf
Overview:
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. Keywords: Analysis of Algorithms, On-line Algorithms, Competitive Analysis, Amortized Analysis, Linear Lists.
Bibliographic Information:
ICSI Technical Report TR-90-037
Bibliographic Reference:
S. Irani. Two Results on the List Update Problem. ICSI Technical Report TR-90-037, August 1990