A Primal-Dual Randomized Algorithm for Weighted Paging
- 1 August 2012
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 59 (4), 1-24
- https://doi.org/10.1145/2339123.2339126
Abstract
We study the weighted version of the classic online paging problem where there is a weight (cost) for fetching each page into the cache. We design a randomized O (log k )-competitive online algorithm for this problem, where k is the cache size. This is the first randomized o ( k )-competitive algorithm and its competitive ratio matches the known lower bound for the problem, up to constant factors. More generally, we design an O (log( k /( k − h + 1)))-competitive online algorithm for the version of the problem where the online algorithm has cache size k and it is compared to an optimal offline solution with cache size h ≤ k . Our solution is based on a two-step approach. We first obtain an O (log k )-competitive fractional algorithm based on an online primal-dual approach. Next, we obtain a randomized algorithm by rounding in an online manner the fractional solution to a probability distribution on the possible cache states. We also give an online primal-dual randomized O (log N )-competitive algorithm for the Metrical Task System problem (MTS) on a weighted star metric on N leaves.Keywords
Funding Information
- BSF (2010426)
- Israel Science Foundation (954/11)
This publication has 24 references indexed in Scilit:
- The Design of Competitive Online Algorithms via a Primal—Dual ApproachFoundations and Trends® in Theoretical Computer Science, 2007
- A unified approach to approximating resource allocation and schedulingJournal of the ACM, 2001
- On the k -server conjectureJournal of the ACM, 1995
- Competitive k-server algorithmsJournal of Computer and System Sciences, 1994
- Thek-server dual and loose competitiveness for pagingAlgorithmica, 1994
- Competitive paging algorithmsJournal of Algorithms, 1991
- A strongly competitive randomized paging algorithmAlgorithmica, 1991
- New Ressults on Server ProblemsSIAM Journal on Discrete Mathematics, 1991
- Competitive algorithms for server problemsJournal of Algorithms, 1990
- Amortized efficiency of list update and paging rulesCommunications of the ACM, 1985