Paging and List Update under Bijective Analysis

the fundamental problems in online computation. As those
they have been extensively studied from practical as well
as theoretical viewpoints.

The competitive ratio fails to distinguish algorithms for
these problems that in practice show significantly different
quality. Bijective analysis, introduced by Angelopoulos,
Dorrigiv and Lopez-Ortiz, is a method to compare online
algorithms without resorting to the offline optimum. We prove,
reinforcing the results observed in practice, that Least
Recently Used (LRU) and Move To Front (MTF) are optimal
according to bijective analysis under the locality of
reference model by Albers, Favrholdt and Giel.

In this talk I will introduce the problems and outline
their optimality proof under bijective analysis.

This is joint work with Spyros Angelopoulos.