Competitive paging with locality of reference
Allan Borodin, Prabhakar Raghavan, Sandy Irani, Baruch Schieber · 1991
The Sleator-Tarjan competitive analysis of paging [19] gives us the ability to make strong theoretical statements about the performance of paging algorithms without making probabilistic assumptions on the input.Nevertheless practitioners voice reservations about the model, citing its inability to discern between is that it is more robust than probabilistic analysis, while more practical than worst-case analysis.With these definitions, Sleator and Tarjan showed that no deterministic on-line paging algorithm can achieve a competitiveness less than k, and that a number of algorithms used in practice (including Least Recently Used or LRU and First-In First-Out or FIFO) are kcompetitive and thus optimal by this measure.