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$.