@inproceedings{e435f86c192f4d128a534b31253f5cee,
title = "The worst page-replacement policy",
abstract = "In this paper, we consider the question: what is the worst possible page-replacement strategy? Our goal is to devise an online strategy that has the highest possible fraction of misses as compared to the worst offline strategy. We show that there is no deterministic, online pagereplacement strategy that is competitive with the worst offline strategy. We give a randomized strategy based on the {"}most-recently-used{"} heuristic, and show that this is the worst possible online page-replacement strategy.",
author = "Kunal Agrawal and Bender, \{Michael A.\} and Fineman, \{Jeremy T.\}",
year = "2007",
doi = "10.1007/978-3-540-72914-3\_13",
language = "English",
isbn = "9783540729136",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "135--145",
booktitle = "Fun with Algorithms - 4th International Conference, FUN 2007, Proceedings",
note = "4th International Conference on Fun with Algorithms, FUN 2007 ; Conference date: 03-06-2007 Through 05-06-2007",
}