Nikhil Bansal, Rohit Khandekar, et al.
SIAM Journal on Computing
In the weighted paging problem there is a weight (cost) for fetching each page into the cache. We design a randomized 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 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 ≤ 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 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 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 O(log2 N)-competitive algorithm of Blum et al. [9]. ©2007 IEEE.
Nikhil Bansal, Rohit Khandekar, et al.
SIAM Journal on Computing
Nikhil Bansal, Zachary Friggstad, et al.
ACM Transactions on Algorithms
Nikhil Bansal, Moshe Lewenstein, et al.
Algorithmica (New York)
Nikhil Bansal, Ho-Leung Chan, et al.
Theoretical Computer Science