Alex Lopez-Ortiz
On the Separation and Equivalence of Paging Strategies: LRU is the sole optimum
Abstract:
On-line paging algorithms are analyzed using competitive analysis, in which the performance of on-line algorithm on a sequence is normalized by the performance of the optimal on-line algorithm on that sequence. This measure can lead to algorithms that focus on the worst case at the expense of the every-day case as well as to lack of separation between algorithms whose performance vary wildly in practice, in particular Least-Recently Used and Flush-When-Full have the same competitive ratio. A long standing open problem in the field is to develop a natural model for online paging, with no pre-ordained knowledge of the request sequence which could separate all known algorithms. In this talk we introduce a new model developed from first principles which separates between LRU and all other paging strategies. The results extend to other online settings such as list update and robot motion planing.
This is joint work with Reza Dorrigiv and Spyros Angelopoulos.