McGeoch L. A., D. Sleator, A Strongly Competitive Randomized Paging Algorithm, Carnegie Mellon University Computer Science technical report CMU-CS-89-122, 1989.
The paging problem is that of deciding which pages to keep in a memory of k pages in order to minimized the number of page faults. We develop the partitioning algorithm, a randomized on-line algorithm for the paging problem. We prove that its expecrted cost on any sequence of requests is within a factor of Hk of optimum. (Hk is the kth harmonic number, which is about ln(k).) No on-line algorithm can perform better by this measure. Our result improves by a factor of two the best previous algorithm.