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

### 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
Full Text: