The Optimality and Complexity of Offline Cache Replacement Policies for Nonuniform Objects

The study of optimal offline cache replacement policies has theoretical significance from which near-optimal but practical cache replacement schemes can be sound established. This paper has re-defined known offline cache replacement policies for nonuniform objects and proposed novel policies. All of them have been evaluated for their optimalities and complexities. The results have showed that the optimal policy has the highest time complexity whereas the other policies are sub-optimal that have lower complexities.