Randomized Algorithms for Weighted Paging

We consider randomized online algorithms for the weighted paging problem. Here we are given a fast memory (cache) of size pages of unit size. Requests arrive for pages over time, and if the requested page is already in the cache the system does nothing, otherwise there is a miss and the system must fetch the page into the cache, possibly evicting some other page. In the weighted version, pages can have different fetching costs. We give an competitive algorithm where is the number of distinct weight classes. Prior to our work competitive algorithms were known only for the unweighted case (i.e. ) due to Fiat et al. [14] and for the case of two weights, due to Irani [15]. We also give an -competitive algorithm for the weighted -paging problem where the online algorithm is compared against the offline algorithm with a (smaller) cache of size . Prior to our work, such a guarantee was known only for the unweighted case due to Young [22]. The key to our results is a novel potential function analysis of the classic randomized marking algorithm for unweighted paging that generalizes easily to the weighted case.