Beyond competitive analysis [on-line algorithms]

Abstract

The competitive analysis of on-line algorithms has been criticized as being too crude and unrealistic. We propose two refinements of competitive analysis an two directions: The first restricts the power of the adversary by allowing only certain input distributions, while the other allows for comparisons between information regimes for on-line decision-making. We illustrate the first with an application to the paging problem; as a by product we characterize completely the work functions of this important special case of the k-server problem. We use the second refinement to explore the power of lookahead in server systems, and the power of visual sensors in robot navigation.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>