There Are Infinitely Many Competitive-Optimal Online List Accessing Algorithms

Authors: 
Ran El-Yaniv
Abstract: 

This paper presents a new family of optimal, 2-competitive, deterministic online list accessing algorithms. This family includes as members the well known MOVE-TO-FRONT (MTF) algorithm, and the recent, more "conservative" algorithm TIMESTAMP due to Albres.

Date: 
June, 1996
Published in: 
Number: 
103