Caching documents with variable sizes and fetching costs: An LP-based approach

We give an integer programming formulation of the paging problem with varying sizes and fetching costs, we use this formulation to provide an alternative proof that a variant of the algorithm greedy-dual-size previously considered (k + 1) /(k − h + 1) competitive against the optimal strategy with cache size h less than or equal to k. Our proof provides further insights to greedy-dual-size. We also indicate how the same integer programming formulation has been recently used to obtain approximation algorithms to the NP-complete offline problem.