Abstract:
We present a randomized on-line algorithm for
the list update problem which 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, list-update.
The final version appeared in:
Information Processing Letters 56 (1995), 135-139.
gz-compressed POSTSCRIPT-file (69 kB, 8 pages)
Back
to Bernhard von Stengel's list of publications