Publication Details
Title: A Combined BIT and TIMESTAMP Algorithm for the List Update Problem
Author: S. Albers, B. von Stengel, and R. Werchner
Group: ICSI Technical Reports
Date: April 1995
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1995/tr-95-016.pdf
Overview:
A simple randomized on-line algorithm for the list update problem is presented that achieves a competitive factor of 1.6, the best known so far. The algorithm makes an initial random choice between two known algorithms that have different worst-case request sequences. The first is the BIT algorithm that, for each item in the list, alternates between moving it to the front of the list and leaving it at its place after it has been requested. The second is a TIMESTAMP algorithm that moves an item in front of less often requested items within the list. Keywords: On-line algorithms, analysis of algorithms, competitive analysis, linear lists, list-update
Bibliographic Information:
ICSI Technical Report TR-95-016
Bibliographic Reference:
S. Albers, B. von Stengel, and R. Werchner. A Combined BIT and TIMESTAMP Algorithm for the List Update Problem. ICSI Technical Report TR-95-016, April 1995
Author: S. Albers, B. von Stengel, and R. Werchner
Group: ICSI Technical Reports
Date: April 1995
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1995/tr-95-016.pdf
Overview:
A simple randomized on-line algorithm for the list update problem is presented that achieves a competitive factor of 1.6, the best known so far. The algorithm makes an initial random choice between two known algorithms that have different worst-case request sequences. The first is the BIT algorithm that, for each item in the list, alternates between moving it to the front of the list and leaving it at its place after it has been requested. The second is a TIMESTAMP algorithm that moves an item in front of less often requested items within the list. Keywords: On-line algorithms, analysis of algorithms, competitive analysis, linear lists, list-update
Bibliographic Information:
ICSI Technical Report TR-95-016
Bibliographic Reference:
S. Albers, B. von Stengel, and R. Werchner. A Combined BIT and TIMESTAMP Algorithm for the List Update Problem. ICSI Technical Report TR-95-016, April 1995