Competitive analysis of the LRFU paging algorithm

We present a competitive analysis of the LRFU paging algorithm, a hybrid of the LRU (Least Recently Used) and LFU (Least Frequently Used) paging algorithms. We show that the competitive ratio of LRFU is k + 1, where 1 is the decay parameter used by the LRFU algorithm, and k is the size of the cache. This supplies, in particular, the rst natural paging algorithms that are competitive but are not optimally competitive, answering a question of Borodin and El-Yaniv. Although LRFU, as it turns out, is not optimally competitive, it is expected to behave well in practice, especially in web applications, as it combines the bene ts of both LRU and LFU