THE K-SERVER DUAL AND LOOSE COMPETITIVENESS FOR PAGING

Weighted caching is a generalization of paging in which the cost to evict an item depends on the item. We study both of these problems as restrictions of the well-known k-server problem, which involves moving servers in a graph in response to requests so as to minimize the distance traveled. We give a deterministic on-line strategy for weighted caching that, on any sequence of requests, given a cache holding k items, incurs a cost within a factor of k/(k - h + 1) of the minimum cost possible given a cache holding h items. The strategy generalizes ''least recently used,'' one of the best paging strategies in practice. The analysis is a primal-dual analysis, the first for an on-line problem, exploiting the linear programming structure of the k-server problem. We introduce loose competitiveness, motivated by Sleator and Tarjan's complaint [ST] that the standard competitive ratios for paging strategies are too high. A k-server strategy is loosely c(k)-competitive if, for any sequence, for almost all k, the cost incurred by the strategy with k servers either is no more than c(k) times the minimum cost or is insignificant. We show that certain paging strategies (including ''least recently used'' and ''first in first out'') that are k-competitive in the standard model are loosely c(k)-competitive provided c(k)/ln k --> infinity and both k/c(k) and c(k) are nondecreasing. We show that the marking algorithm, a randomized paging strategy that is THETA(ln k)-competitive in the standard model, is loosely c(k)-competitive provided k - 2 ln ln k --> infinity and both 2 ln k - c(k) and c(k) are nondecreasing.