Limited bookmark randomized online algorithms for the paging problem

摘要

An efficient randomized online algorithm for the paging problem for cache size 2 is given, which is 3/2-competitive against an oblivious adversary. The algorithm keeps track of at most one page in slow memory at any time. A lower bound of 37/24≈1.5416 is give for the competitiveness of any trackless online algorithm for the same problem, i.e., an algorithm that keeps track of no page outside the cache.