The work function algorithm for the paging problem

The paging problem is that of deciding which pages to keep in a memory of pages in order to minimize the number of page faults in a two-level store. It is a special case of the famous -server problem. In this paper, we firstly show that is -competitive for the -server problem where the distances between two points are all in (), and thus is -competitive for the paging problem. And we further show that the well known for the paging problem is just a special case of .