Equitable revisited. (English) Zbl 1151.68743

Arge, Lars (ed.) et al., Algorithms – ESA 2007. 15th annual European symposium, Eilat, Israel, October 8–10, 2007, Proceedings. Berlin: Springer (ISBN 978-3-540-75519-7/pbk). Lecture Notes in Computer Science 4698, 419-426 (2007).
Summary: The randomized \(k\)-paging algorithm Equitable given by D. Achlioptas, M. Chrobak and J. Noga [Theor. Comput. Sci. 234, No. 1–2, 203–218 (2000; Zbl 0944.68194)] is \(H _{k }\)-competitive and uses \(O(k ^{2} \log k)\) memory. This competitive ratio is best possible. The randomized algorithm RMark given by A. Fiat et al. [J. Algorithms 12, No. 4, 685–699 (1991; Zbl 0753.68018)] is \((2H _{k } - 1)\)-competitive, but only uses \(O(k)\) memory. A. Borodin and R. El Yaniv [Online computation and competitive analysis. Cambridge: Cambridge University Press (1998; Zbl 0931.68015)] list as an open question whether there exists an \(H _{k }\)-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.
For the entire collection see [Zbl 1130.68001].


68W20 Randomized algorithms
68W40 Analysis of algorithms
Full Text: DOI