Tight Results for Online Convex Paging

Abstract

The online convex paging problem models a broad class of cost  functions for the classical paging problem. In particular, it naturally  captures fairness constraints: e.g., that no specific page (or groups of  pages) suffers an ``unfairly'' high number of evictions by considering
$\ell_p$ norms of  eviction vectors for $p>1$. The case of the $\ell_\infty$ norm has also been of special interest, and is called  min-max paging.

We give tight upper and lower bounds for the convex paging problem for a  broad class of convex functions.  Prior to our work, only fractional algorithms were known for this general setting. Moreover, our general result also improves on prior works for special cases of the problem.   For example, it implies that the randomized competitive ratio of the  min-max paging problem is $\Theta(\log k\log n)$; this improves both the  upper bound and the lower bound given in prior work by logarithmic factors. It also shows that the randomized and deterministic competitive
ratios for $\ell_p$-norm paging are $\Theta(p\log k)$ and $\Theta(pk)$  respectively.

This is joint work with Anupam Gupta and Debmalya Panigrahi.