Beyond competitive analysis
The competitive analysis of online algorithms has been criticized as being too crude and unrealistic. We propose refinements of competitive analysis in two directions: The rst restricts the power of the adversary by allowing only certain input distributions, while the other allows for comparisons between information regimes for online decision-making. We illustrate the rst with an application to the paging problem; as a byproduct 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 and task systems.
competitive analysis online algorithms paging problem metrical task systems