Abstract:
The optimal competitive ratio for a randomized online list update
algorithm is known to be at least 1.5 and at most 1.6, but the
remaining gap is not yet closed.
We present a new lower bound of 1.50084 for the partial cost model.
The construction is based on game trees with incomplete information,
which seem to be generally useful for the competitive analysis of
online algorithms.
Keywords:
On-line algorithms, analysis of algorithms,
competitive analysis, list-update.
Theoretical Computer Science (2001), Vol. 268, 3-16.
gz-compressed POSTSCRIPT-file (81 kB, 14 pages)
Back
to Bernhard von Stengel's list of publications