The randomized k-paging algorithm EQUITABLE given by Achlioptas et al. is Hk-competitive and uses O(k2 log k) memory. This competitive ratio is best possible. The randomized algorithm RMARK given by Fiat et al. is (2Hk - 1)-competitive, but only uses O(k) memory. Borodin and El Yaniv [6] list as an open question whether there exists an Hk-competitive randomized algorithm which requires O(k) memory for k-paging. In this paper we answer this question in the affirmative by giving a modification of EQUITABLE.
['Wolfgang W. Bein', 'Lawrence L. Larmore', 'John Noga']
Equitable revisited