Equitable revisited. (English) Zbl 1151.68743

Bein, Wolfgang; Larmore, Lawrence L.; Noga, John

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].

MSC:

68W20	Randomized algorithms
68W40	Analysis of algorithms

Keywords:

design of algorithms; online algorithms; paging; randomization

Citations:

Zbl 0944.68194; Zbl 0753.68018; Zbl 0931.68015