In the paging problem we have to manage a two-level memory system, in which
the first level has short access time but can hold only up to k pages, whi
le the second level is very large but slow. We use competitive analysis to
study the relative performance of the two best known algorithms for paging,
LRU and FIFO. Sleator and Tarjan proved that the competitive ratio of LRU
and FIFO is k. In practice, however, LRU is known to perform much better th
an FIFO. It is believed that the superiority of LRU can be attributed to lo
cality of reference exhibited in request sequences. In order to study this
phenomenon, Borodin et al. [2] refined the competitive approach by introduc
ing the concept of access graphs. They conjectured that the competitive rat
io of LRU on each access graph is less than or equal to the competitive rat
io of FIFO. We prove this conjecture in this paper.