List Update with Locality of Reference
[.pdf]
Abstract
It is known that in practice, request sequences for the list update problem exhibit a certain degree of locality of reference.
Motivated by this observation we apply the locality of reference model for the paging problem due to Albers et al. [STOC 2002/JCSS 2005] in conjunction with bijective analysis [SODA 2007] to list update.
Using this framework, we prove that Move-to-Front (MTF) is the unique optimal algorithm for list update.
This addresses the open question of defining an appropriate model for capturing locality of reference in the context of list update [Hester and Hirschberg ACM Comp. Surv. 1985].
Our results hold both for the standard cost function of Sleator and Tarjan [CACM 1985] and the improved cost function proposed independently by Martinez and Roura [TCS 2000] and Munro [ESA 2000].
This result resolves an open problem of Martinez and Roura, namely proposing a measure which can successfully separate MTF from all other list-update algorithms.
Bibtex Entry
