Abstract
In the weighted paging problem there is a weight (cost) for fetching each page into the cache. We design a randomized {\rm O}(\log k)-competitive online algorithm for the weighted paging problem, where k is the cache size. This is the first randomized o(k)-competitive algorithm and its competitiveness matches the known lower bound on the problem. More generally, we design an {\rm O}(\log (k/(k - h + 1)))-competitive online algorithm for the version of the problem where the online algorithm has cache size k and the offline algorithm has cache size h \leqslant k. Weighted paging is a special case (weighted star metric) of the well known k-server problem for which it is a major open question whether randomization can be useful in obtaining sublinear competitive algorithms. Therefore, abstracting and extending the insights from paging is a key step in the resolution of the k-server problem.
Our solution for the weighted paging problem is based on a two-step approach. In the first step we obtain an {\rm O}(\log k)-competitive fractional algorithm which is based on a novel online primal-dual approach. In the second step we obtain a randomized algorithm by rounding online the fractional solution to an actual distribution on integral cache solutions. We conclude with a randomized {\rm O}(\log N)-competitive algorithm for the well studied Metrical Task System problem (MTS) on a metric defined by a weighted star on N leaves, improving upon a previous {\rm O}(\log ^2 N)-competitive algorithm of Blum et al.
Original language | English |
---|---|
Title of host publication | Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07, Providence RI, USA, October 20-23, 2007) |
Publisher | IEEE Computer Society |
Pages | 507-517 |
ISBN (Print) | 0-7695-3010-9 |
Publication status | Published - 2007 |