  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.

Data Structures and Algorithms