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 in [4] and [5] is (k+1)/(k‐h+1)competitive against the optimal strategy with cache size h≤ k . Our proof provides further insights to greedy‐dual‐size. We also indicate how the same integer programming formulation has been recently used [1], [2] to obtain approximation algorithms to the NP‐complete “offline” problem.