D. D. Sleator, R. E. Tarjan, Amortized Efficiency Of List Update and Paging Rules, Communications of the ACM, Vol. 28, No. 2, 1985
In this article we study the amortized efficiency of the “move-to-front” and similar rules for dynamically maintaining a linear list. Under the assumption that accessing the ith element from the front of the list takes e(i) time, we show that move-to-front is within a constant factor of optimum among a wide class of list maintenance rules. Other natural heuristics, such as the transpose and frequency count rules, do not share this property. We generalize our results to show that move-to-front is within a constant factor of optimum as long as the access cost is a convex function. We also study paging, a setting in which the access cost is not convex. The paging rule corresponding to move-to-front is the “least recently used“ replacement rule. We analyze the amortized complexity of LRU, showing that its efficiency differs from that of the off-line paging rule (Belady’s MlN algorithm) by a factor that depends on the size of fast memory. No on-line paging algorithm has better amortized performance.