On the Separation and Equivalence of Paging Strategies, Spyros Angelopoulos, Reza Dorrigiv, and A. López-Ortiz. To appear in Proceedings of 18^th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2007. [PDF file]

Abstract.
It has been experimentally observed that LRU and variants thereof are the preferred strategies for on-line paging. However, under most proposed performance measures for on-line algorithms the performance of LRU is the same as that of many other strategies which are inferior in practice. In this paper we first show that any performance measure which does not include a partition or implied distribution of the input sequences of a given length is unlikely to distinguish between any two lazy paging algorithms as their performance is identical in a very strong sense. This provides a theoretical justification for the use of a more refined measure. Building upon the ideas of concave analysis by Albers et al., we prove strict separation between LRU and all other paging strategies. That is, we show that LRU is the unique optimum strategy for paging under a deterministic model. This provides full theoretical backing to the empirical observation that LRU is preferable in practice.