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.

By: Nikhil Bansal

Published in: RC24109 in 2006


This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.


Questions about this service can be mailed to reports@us.ibm.com .