Online Min-Max Paging

Motivated by fairness requirements in communication networks, we introduce a natural variant of the online paging problem, called 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 Ω(log(n)) and its deterministic competitive ratio is Ω(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 poly(log(k)) factor. We also give a randomized rounding algorithm that results in a O(log 2 n log k)-competitive algorithm.