Technical Report CS0607

Title: A New Measure for the Study of Online Algorithms
Authors: S. Ben-David and A. Borodin
Abstract: An accepted measure for the performence of an online algorithm is the "competitive ratio" introduced by Sleator and Tarjan. This measure is well motivated and has led to the development of a significant mathematical theory for online algorithms. We point out some counter-intuitive features of this measure: Its dependence upon memory and its inability to reflect the benefits of lookahead. We offer an alternative measure that exhibits a more intuitive behaviour. In particular, we demonstrate the use of our new measure by analysing the tradeoff between the amortized cost of an online algorithm and the amount of lookahead. We also derive online algorithms for the K-server problem on any graph, which, relative to the new measure, are optimal among all online algorithms (up to a factor of 2) and are within a factor of 2K from the optimal offline performance.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1990
To the main CS technical reports page

Computer science department, Technion