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 approximate to 1.5416 is given 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. (C) 2000 Elsevier Science B.V. All rights reserved.
online algorithms paging design of algorithms randomized algorithms