Competitive analysis of randomized paging algorithms
Open accessThe claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The (e/(e-1))-competitive randomized online algorithm for ski-rental [12] and the H_k-competitive randomized online algorithm for caching [1, 16], give a (H_k + e/(e-1))-competitive randomized online algorithm for rental caching.
“Corollary 3.7. The ( e e -1 ) -competitive randomized online algorithm for ski-rental [12] and the H k -competitive randomized online algorithm for caching [1, 16], give a ( H k + e e -1 ) -competitive randomized online algorithm for rental caching.”
From Caching with rental cost and zapping (2012) · cites this paper as [1]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Fiat, A., Karp, R. M., Luby, M., McGeoch, L. A., Sleator, D. D., & Young, N. E. (1991) · Journal of Algorithms · doi:10.1016/0196-6774(91)90041-v · Cited by 457 · see citing works
A strongly competitive randomized paging algorithm
McGeoch, L. A., & Sleator, D. D. (1991) · Algorithmica · doi:10.1007/bf01759073 · Cited by 238 · see citing works
Flagged first, then by citations
Research works printed but not linked: 13
- A. Borodin, S. Irani, P. Raghavan, B. Schieber, Competitive paging with locality of reference, in: Proc. 23rd ACM Symp. on Theory of Computing, 1991, pp. 249-259.
- M. Chrobak, L.L. Larmore, Generosity helps or an 11-competitive algorithm for three servers, J. Algorithms 16 (1994) 234-263; also in Proc. ACM-SIAM Symp. on Discrete Algorithms, 1992b, pp. 196-202.
- S. Irani, S. Seiden, Randomized algorithms for metrical task systems, in: Proc. 4th Workshop on Algorithms and Data Structures, 1995, pp. 159-170.
- S. Irani, A. Karlin, S. Phillips, Strongly competitive algorithms for paging with locality of reference, in: 3rd Annu. ACM-SIAM Symp. on Discrete Algorithms, 1992, pp. 228-236.
- A. Karlin, S. Phillips, P. Raghavan, Markov paging, in: Proc. 33rd IEEE Symp. on Foundations of Computer Science, 1992, pp. 208-217.
- E. Koutsoupias, C. Papadimitriou, Beyond competitive analysis, in: Proc. 35th Symp. on Foundations of Computer Science, 1994a, pp. 394-400.
- E. Koutsoupias, C. Papadimitriou, On the k-server conjecture, in: Proc. 26th Symp. on Theory of Computing, 1994, pp. 507-511.
- H. Kuhn, Extensive games and the problem of information, in: Kuhn, H., Tucker, A. (Eds.), Con- tributions to the Theory of Games, Princeton University Press, 1953, pp. 193-216.
- C. Lund, N. Reingold, Linear programs for randomized on-line algorithms, in: Proc. 5th ACM-SIAM Symp. on Discrete Algorithms, 1994a, pp. 382-391.
- C. Lund, N. Reingold, J. Westbrook, D. Yan, On-line distributed data management, in: Proc. European Symp. on Algorithms, 1994b, pp. 202-214.
- P. Raghavan, M. Snir, Memory versus randomization in online algorithms, in: 16th International Colloquium on Automata, Languages, and Programming, Lecture Notes in Computer Science, vol. 372. Springer, Berlin, 1989, pp. 687-703.
- D. Sleator, R.E. Tarjan, Amortized e ciency of list update and paging rules, Communications of the ACM, 28 (1985) 202-208.
- N. Young, On-line caching as cache size varies, in: Proc. 2nd Ann. ACM-SIAM Symp. on Discrete Algorithms, 1991, pp. 241-250.
Cited by
Sorted by citations
Competitive Caching with Machine Learned Advice
Lykouris, T., & Vassilvitskii, S. (2021) · Journal of the ACM · doi:10.1145/3447579 · Cited by 172 · see citing works
Caching with rental cost and zapping
Khare, M., & Young, N. E. (2012) · arXiv · doi:10.48550/arxiv.1208.2724 · Cited by 1 · see citing works
“number, for any randomized algorithm and give a 2Hk-competitive Randomized Marking algorithm. It was later proved that the tight competitive ratio of Randomized Marking is 2Hk −1 by Achlioptas et al. [1]. McGeoch and Sleator [16] and Achlioptas et al. [1] give optimal Hk-competitive randomized algorithms for paging. F…”
Influential
- Authors
- Achlioptas, D., Chrobak, M., & Noga, J.
- Affiliations
- University of Toronto (CA)
- University of California, Riverside (US)
- Corresponding author
- Noga, John
- ORCID
- Achlioptas, Dimitris
- Venue
- Theoretical Computer Science
- Publisher
- Elsevier BV
- Published
- 2000-03
- Volume
- 234
- Issue
- 1-2
- Pages
- 203-218
- ISSN
- 0304-3975 (ISSN-L)
- OpenAlex
- W1998843748
- Cited by
- 127
- References
- 2
- Citations by year
- 2026: 1 · 2025: 3 · 2024: 2 · 2023: 1 · 2022: 9 · 2021: 9 · 2020: 4 · 2019: 4 · 2018: 2 · 2017: 7 · 2016: 3 · 2015: 7 · 2014: 4 · 2013: 2 · 2012: 9
- FWCI
- 5.63
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Licence
- Locations
- Theoretical Computer Science (publishedVersion)
- Funders
- National Science Foundation (9503498)
- Natural Sciences and Engineering Research Council of Canada
- Topics
- Physical Sciences › Computer Science › Computer Networks and Communications › Optimization and Search Problems
- Physical Sciences › Computer Science › Artificial Intelligence › Algorithms and Data Compression
- Physical Sciences › Computer Science › Computer Networks and Communications › Distributed systems and fault tolerance
- Keywords
- cache replacement, randomized algorithms, competitive ratio, work function, marking algorithm, competitive analysis, memory hierarchy, cache misses
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
