A primal-dual randomized algorithm for weighted paging

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