Competitive snoopy caching
The DOI matches its Crossref record; 13 of the 13 references it cites were found in a registry or an index.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
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?
In the citing paper
“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 [12]
In the citing paper
“Corollary 3.6. The 2 -competitive deterministic online algorithm for ski-rental [12] and the k -competitive deterministic online algorithm for caching [17], give a ( k +2) -competitive deterministic online algorithm for rental caching.”
From Caching with rental cost and zapping (2012) · cites this paper as [12]
In the citing paper
“Corollary 3.3. There is a ( e e -1 ) -competitive randomized algorithm for rental caching with infinite cache.”
From Caching with rental cost and zapping (2012) · cites this paper as [12]
In the citing paper
“Corollary 3.2. ALG ∞ is a 2 -competitive deterministic algorithm for rental caching with infinite cache.”
From Caching with rental cost and zapping (2012) · cites this paper as [12]
In the citing paper
“Second, using similar reasoning, note that we may consider only strategies that are monotone over time with respect to majorization [11], i.e., strategies such that for any two times t ≤ t ′ we have”
From Rent, Lease, or Buy: Randomized Algorithms for Multislope Ski Rental (2012) · cites this paper as [11]
Citations
Cites
Amortized efficiency of list update and paging rules
Sleator, D. D., & Tarjan, R. E. (1985) · Communications of the ACM · doi:10.1145/2786.2793 · Cited by 2,123
Self-citationA study of replacement algorithms for a virtual-storage computer
Belady, L. A. (1966) · IBM Systems Journal · doi:10.1147/sj.52.0078 · Cited by 1,659
A low-overhead coherence solution for multiprocessors with private cache memories
Papamarcos, M. S., & Patel, J. H. (1998) · 25 years of the international symposia on Computer architecture (selected papers) · doi:10.1145/285930.285987 · Cited by 405
Using cache memory to reduce processor-memory traffic
Goodman, J. R. (1998) · doi:10.1145/285930.285984 · Cited by 395
Using cache memory to reduce processor-memory traffic
Goodman, J. R. (1983) · Proceedings - International Symposium on Computer Architecture/Proceedings · doi:10.1145/800046.801647 · Cited by 307
Implementing a cache consistency protocol
Katz, R. H., Eggers, S. J., Wood, D. A., et al. (1985) · ACM SIGARCH Computer Architecture News · doi:10.1145/327070.327237 · Cited by 255
A low-overhead coherence solution for multiprocessors with private cache memories
Papamarcos, M. S., & Patel, J. H. (1984) · Proceedings - International Symposium on Computer Architecture/Proceedings · doi:10.1145/800015.808204 · Cited by 246
Dynamic decentralized cache schemes for mimd parallel processors
Rudolph, L., & Segall, Z. (1984) · ACM SIGARCH Computer Architecture News · doi:10.1145/773453.808203 · Cited by 213
Self-citationAmortized analyses of self-organizing sequential search heuristics
Bentley, J. L., & McGeoch, C. C. (1985) · Communications of the ACM · doi:10.1145/3341.3349 · Cited by 139
Dynamic decentralized cache schemes for mimd parallel processors
Rudolph, L., & Segall, Z. (1984) · Proceedings - International Symposium on Computer Architecture/Proceedings · doi:10.1145/800015.808203 · Cited by 119
Self-citation
Cited by
Items 601–619 of 619
A Learning-Augmented Algorithm for the Parking Permit Problem with Three Permit Types
Yaroslav, K., & Kononov, A. V. (2024) · Lecture notes in computer science · doi:10.1007/978-3-031-62792-7_8 · Cited by 1
Risk-Reward Models for Two-option Online Leasing Problem
Wu, J., & Zhang, Y. (2024) · International Conference on Information Management and Management Science (IMMS) · doi:10.1145/3695652.3695653
“Karlin et al. [16] considered randomization in the model and found an improved performance ratio, showing an 𝑒 /( 1 − 𝑒 ) competitive online randomized algorithm.”
Competitive Ratio for Portfolio Management
Deng, X. (2024) · Encyclopedia of Optimization · doi:10.1007/978-3-030-54621-2_74-1
MPMD on Two Sources with Lookahead
Sun, E., Wang, B., Xue, Q., Zhao, M., & Zhu, Z. (2025) · Lecture notes in computer science · doi:10.1007/978-981-96-1090-7_15
Lot scheduling on a single machine to minimize total weighted completion time
Zheng, F., Li, N., Xu, Y., et al. (2025) · RAIRO - Operations Research · doi:10.1051/ro/2025049
Baisakh, Swain, B. P., Patel, N., et al. (2025) · International Conference on Emerging Systems and Intelligent Computing (ESIC) · doi:10.1109/esic64052.2025.10962784
“The early research exploration of the online list update algorithms have primarily focused on the theoretical aspects [22], [23] of the problem which involve competitive analysis, cost models, different designing paradigms such as randomization, approximation.”
Group Rent-or-Buy: the Benefits of Having Grouped Consumers
Meng, L.-Y., Wang, C., & Ye, Q. (2025) · Journal of the Operations Research Society of China · doi:10.1007/s40305-025-00590-3
Improved Learning-Augmented Algorithms and (Tight) Lower Bounds for Multi-Option Ski Rental Problem
Shin, Y.-H., Lee, C., Lee, G., & An, H.-C. (2025) · ACM Transactions on Algorithms · doi:10.1145/3763239 · Cited by 11
Beneich, C., & Douiri, S. M. (2026) · RAIRO - Operations Research · doi:10.1051/ro/2026002
Balancing fairness: learning with conflicting objectives and user feedback
Awasthi, P., Cortes, C., Mansour, Y., & Mohri, M. (2026) · Annals of Mathematics and Artificial Intelligence · doi:10.1007/s10472-026-10004-6 · Cited by 1
“At each vertex, the algorithm faces the classical ski-rental problem, for which there exists a deterministic algorithm that is 2 -competitive with the optimal solution (Karlin et al., 1988).”
Performance guaranteeing algorithms for solving online decision problems in financial systems
Schroeder, P. (2019) · theses.fr (ABES) · doi:10.70675/9976a622z13e6z4feaz8d69zbb5172afa95a
Baisakh, B., Mohapatra, H., & Patel, N. (2026) · OPSEARCH · doi:10.1007/s12597-026-01181-3
To Adapt or Not to Adapt, That is the Ski Question
Chesetti, Y., & Pandey, P. (2026) · Proceedings of the ACM on Management of Data · doi:10.1145/3802121 · Cited by 1
Understanding Cross-Cloud Interconnects: Hands-On Measurements and Cost Optimization
Eliav, E., Keslassy, I., Breitgand, D., Lorenz, D. H., & Weit, A. (2026) · IEEE ... International Conference on Cloud Computing · doi:10.1109/cloud72782.2026.00024
Tiedemann, M. (2015) · eDiss (Georg-August-Universität Göttingen) · doi:10.53846/goediss-5046
Models for Parallel Computation in Multi-Core, Heterogeneous, and Ultra Wide-Word Architectures
Salinger, A. (2013) · UWSpace (University of Waterloo)
Geometric On-line Ray Searching Under Probability of Placement Scenarios
Liu, Y. (2010) · UWSpace (University of Waterloo)
Locks, Directories, and Weak Coherence—a Recipe for Scalable Shared Memory Architectures
Lee, J., & Ramachandran, U. (1992) · Springer eBooks · doi:10.1007/978-1-4615-3604-8_4
Shin, Y., Lee, C., Lee, G., & An, H.-C. (2023) · arXiv · doi:10.48550/arxiv.2302.06832
Metadata
- Authors
- Karlin, A. R., Manasse, M. S., Rudolph, L., & Sleator, D. D.
- Affiliations
- Stanford University (US)
- Defense Engineering Corporation (United States) (US)
- Hebrew University of Jerusalem (IL)
- Carnegie Mellon University (US)
- Venue
- Algorithmica
- Published
- 1988-11
- Volume
- 3
- Issue
- 1-4
- Pages
- 79-119
- ISSN
- 0178-4617 (ISSN-L)
- 1432-0541
- OpenAlex
- W2011670396
- Cited by
- 631
- References
- 13
- Citations by year
- 2026: 7 · 2025: 9 · 2024: 12 · 2023: 9 · 2022: 13 · 2021: 9 · 2020: 11 · 2019: 16 · 2018: 12 · 2017: 16 · 2016: 16 · 2015: 17 · 2014: 20 · 2013: 28 · 2012: 21
- FWCI
- 12.30
- Type
- journal article
- Language
- en
- Open access
- closed
- Licence
- www.springer.com/tdm (tdm)
- Locations
- Algorithmica (publishedVersion)
- Topics
- Physical Sciences › Mathematics › Theoretical Computer Science › Optimization and Search Problems
- Physical Sciences › Computer Science › Hardware and Architecture › Parallel Computing and Optimization Techniques
- Physical Sciences › Mathematics › Theoretical Computer Science › Algorithms and Data Compression
- Keywords
- online algorithms, competitive analysis, cache eviction, lower bounds
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
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.