Technical Report Number
We report a number of new results in generalized caching. This problem arises in modern computer networks in which data objects of various sizes are transmitted frequently. First it is shown that its optimal solution is NP-complete. Then we explore two methods of obtaining nearly optimal answers based on the dynamic programming algorithm that we provided in . These methods enable a trade-off between optimality and speed. It is also shown that LFD (the longest forward distance algorithm which is the optimal policy in the classical case), is no longer optimal but is competitive. We also prove that LRU remains competitive in the generalized case. This is an extension of a famous results by Sleator and Tarjan  on LRU. Finally, it is confirmed in the general case that prefetch does not reduce the total cost if "cost" reflects only the number of bytes transmitted.
Hosseini-Khayat, Saied, "New Results on Generalized Caching" Report Number: WUCS-96-25 (1996). All Computer Science and Engineering Research.
Permanent URL: http://dx.doi.org/10.7936/K7JQ0Z75