Paging and list update with locality of reference

and some of its variants are the preferred strategies for on-line paging. This is largely due to the fact that typical request sequences
exhibit a certain degree of locality of reference. However, under most of the known measures for comparison of online algorithms, LRU has the same performance as strategies which are clearly inferior in practice. A similar situation arises in the list update problem, where Move-To-Front (MTF) performs well in sequences of high locality of reference, yet it cannot be separated from other algorithms under the cost model proposed independently by Martinez and Roura, and Munro.

In this talk I will describe a natural measure for comparison of online algorithms under which LRU and MTF are provably the unique optimal algorithms for paging and list update, respectively. This line of research aims to bridge (or at least narrow) the disconnect which appears occasionally between competitive analysis and the performance of online algorithms in "the real world".

Joint work with Reza Dorrigiv and Alejandro Lopez-Ortiz.