Paging with Request Sets

A generalized paging problem is considered. Each request is expressed as a set of $u$ pages. In order to satisfy the request, at least one of these pages must be in the cache. Therefore, on a page fault, the algorithm must load into the cache at least one page out of the $u$ pages given in the request. The problem arises in systems in which requests can be serviced by various utilities (e.g., a request for a data that lies in various web-pages) and a single utility can service many requests (e.g., a web-page containing various data). The server has the freedom to select the utility that will service the next request and hopefully additional requests in the future. The case $u=1$ is simply the classical paging problem, which is known to be polynomially solvable. We show that for any $u>1$ the offline problem is NP-hard and hard to approximate if the cache size $k$ is part of the input, but solvable in polynomial time for constant values of $k$. We consider mainly online algorithms, and design competitive algorithms for arbitrary values of $k,u$. We study in more detail the cases where $u$ and $k$ are small. %We further study two modifications of the problem. We also give an algorithm which uses resource augmentation and which is asymptotically optimal for $u=2$