Randomized Weighted Caching with Two Page Weights

Randomized Weighted Caching with Two Page Weights

0.00 Avg rating—0 Votes
Article ID: iaor20121108
Volume: 32
Issue: 4
Start Page Number: 624
End Page Number: 640
Publication Date: Apr 2002
Journal: Algorithmica
Authors:
Keywords: caching algorithm, memory
Abstract:

We consider a special case of the weighted caching problem where the weight of every page is either 1 or some fixed number M > 1 . We present a randomized algorithm which achieves a competitive ratio which is O( log k) where k is the number of pages which can fit in the cache.

Reviews

Required fields are marked *. Your email address will not be published.