Online Min-Max Paging

Download PDF

Motivated by fairness requirements in communication networks, we introduce a natural variant of the online paging problem, called \textit{min-max} paging, where the objective is to minimize the maximum number of faults on any page. While the classical paging problem, whose objective is to minimize the total number of faults, admits k-competitive deterministic and O(\log k)-competitive randomized algorithms, we show that min-max paging does not admit a c(k)-competitive algorithm for any function c. Specifically, we prove that the randomized competitive ratio of min-max paging is \Omega(\log(n)) and its deterministic competitive ratio is \Omega(k\log(n)/\log(k)), where n is the total number of pages ever requested.
We design a fractional algorithm for paging with a more general objective -- minimize the value of an n-variate differentiable convex function applied to the vector of the number of faults on each page. This gives an O(\log(n)\log(k))-competitive fractional algorithm for min-max paging. We show how to round such a fractional algorithm with at most a k factor loss in the competitive ratio, resulting in a deterministic O(k\log(n)\log(k))-competitive algorithm for min-max paging. This matches our lower bound modulo a \mathrm{poly}(\log(k)) factor. We also give a randomized rounding algorithm that results in a O(\log^2 n \log k)-competitive algorithm.