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 501–600 of 619
A Theory of Learning with Competing Objectives and User Feedback
Awasthi, P., Cortes, C., Mansour, Y., & Mohri, M. (2024) · Lecture notes in computer science · doi:10.1007/978-3-031-63735-3_2 · Cited by 1
“At each vertex the algorithm is faced with the classical ski-rental problem for which there exists a deterministic algorithm that is 2 -competitive with optimal algorithm (Karlin et al. 1988).”
MethodCan competitive analysis be made competitive
Borodin, A. (1992) · Conference of the Centre for Advanced Studies on Collaborative Research · Cited by 1
Competitive algorithms for the weighted server problem
Fiat, A., & Ricklin, M. (2002) · Israel Symposium on Theory and Computing Systems (ISTCS) · doi:10.1109/istcs.1993.253459 · Cited by 1
Adaptive step size selection for optimization via the ski rental problem
Aghazadeh, A., Ayremlou, A., Calderon, D. D., et al. (2013) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.2013.6638691 · Cited by 1
“The main feature of our algorithm is that it can be applied to a generic optimization algorithm.”
MethodAn evaluation of hardware-based and compiler-controlled optimizations of snooping cache protocols
Dahlgren, F., Skeppstedt, J., & Stenström, P. (1998) · Future Generation Computer Systems · doi:10.1016/s0167-739x(98)00002-8 · Cited by 1
Preemptively Guessing the Center
Konrad, C., & Tonoyan, T. (2018) · Lecture notes in computer science · doi:10.1007/978-3-319-96151-4_24 · Cited by 1
“Again, note that ∆ X A = B X A − W/2 = W · (RXA − 1)/2.”
BackgroundMethodInfluentialOn packet scheduling with adversarial jamming and speedup
Böhm, M., Jeż, Ł., Sgall, J., et al. (2019) · Annals of Operations Research · doi:10.1007/s10479-019-03153-x · Cited by 1
Competitive Algorithms for Bulk Allocation under Uncertainty: The Caterer's Problem
Kodialam, A. (2020) · SIAM Undergraduate Research Online · doi:10.1137/20s1355549 · Cited by 1
“The most common approach to handling uncertainty in the input is the idea of competitive ratio [8].”
BackgroundDelta Coherence Protocols: The Home Update Protocol
Williams, C., Reynolds, P. F., & de Supinoki, B. (2000) · doi:10.2172/793578 · Cited by 1
Downstream resource allocation in docsis 3.0 channel bonded networks
Martin, J., & Moser, S. (2011) · TigerPrints (Clemson University) · Cited by 1
An on-line algorithm for navigating in unknown terrain
Chan, K.-F., & Lam, T. (1991) · Lecture notes in computer science · doi:10.1007/3-540-54945-5_56 · Cited by 1
“Competitive analysis was first introduced by Sleator and Targan [15] for evaluating different heuristics for maintaining a search list, and was then widely recognized to be better than the traditional worst-case and average-case analysis for studying a variety of on-line problems [2, 4, 6, 7 , 10, 13].”
MethodPaging on a RAM with Limited Resources
Lai, T. W. (2002) · Lecture notes in computer science · doi:10.1007/3-540-45471-3_43
“[10] proposed the Flush-When-Full (FWF) algorithm, which evicts all pages in the cache when the cache is full and a requested page causes a fault.”
MethodNew Results on the k-Truck Problem
Ma, W., Xu, Y., You, J., et al. (2002) · Lecture notes in computer science · doi:10.1007/3-540-45655-4_54 · Cited by 1
The list update problem and the retrieval of sets
d’Amore, F., & Liberatore, V. (1994) · Theoretical Computer Science · doi:10.1016/0304-3975(94)00010-7 · Cited by 1
“This is actually one of the first competitiveness analyses, even if at that time the term "competitive" [ 8 ] had not been introduced yet.”
BackgroundInfluentialCompetitive algorithms for the bicriteria k -server problem
Flammini, M., & Nicosia, G. (2006) · Discrete Applied Mathematics · doi:10.1016/j.dam.2005.04.018 · Cited by 1
clever or smart: Strategies for the online target date assignment problem
Gassner, E., Hatzl, J., Krumke, S. O., et al. (2009) · Discrete Applied Mathematics · doi:10.1016/j.dam.2009.08.014 · Cited by 1
Competitive Analysis of Two Special Bahncard Replacement Problem
Ding, L., Liu, X., & Kang, W. (2009) · Journal of Applied Sciences · doi:10.3923/jas.2009.1185.1189 · Cited by 1
Strategic directions in research in theory of computing
Condon, A., Fich, F. E., Frederickson, G. N., Goldberg, A. V., Johnson, D. S., Loui, M. C., Mahaney, S., Raghavan, P., Savage, J. E., Selman, A. L., et al. (1997) · ACM SIGACT News · doi:10.1145/262301.262310 · Cited by 2
“One ma-jot contribution is the notion of competitive analysis Karlin et al. 1988, and a celebrated achievement is the design of a competitive k-server algorithm Koutsoupias and Papadim-itriou 1994.”
BackgroundRisk Reward Analysis of Online Simplified Bahncard Problem with Interest Rate
Xin, C., Ma, W.-M., & Yang, L. (2007) · International Conference on Machine Learning and Cybernetics · doi:10.1109/icmlc.2007.4370142 · Cited by 1
“[4] coined the term competitive analysis.”
Applied Methods for the Vehicle Positioning Problem
Cardonha, C. (2012) · doi:10.14279/depositonce-3141 · Cited by 1
Online Quantity Flexibility Contract Model and its Competitive Analysis
Xin, C., Ma, W., & Liu, B. (2008) · IEEE Congress on Evolutionary Computation (CEC) · doi:10.1109/cec.2008.4631066 · Cited by 1
“On-line problems had already been investigated in the 1970s and early 1980s but an extensive and systematic study started only when Sleator and Tarjan [8] suggested comparing an on-line algorithm to an optimal off-line algorithm and Karlin et al. [11] coined the term competitive analysis.”
BackgroundAn Algorithm for Dynamic Data Distribution, Preliminary Version
Wolfson, O., & Jajodia, S. (1992) · doi:10.21236/ada252875 · Cited by 1
On the dynamic allocation of mobile agents by on-line task scheduling
Yang, X., Ma, W., You, J., et al. (2002) · Proceedings - IEEE International Parallel and Distributed Processing Symposium · doi:10.1109/ipdps.2002.1016628 · Cited by 1
“In a study of the competitive snoopy caching problem [13], researchers compared the performance of an on-line algorithm ) (A to an optimal off-line strategy ) (OPT .”
On the optimality of Least Recently Used
Hiller, B., & Vredeveld, T. (2008) · Cited by 1
Lu, X. (2013) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 1
Simple and Effective Dynamic Provisioning for Power-Proportional Data CentersPreprint
Lu, T., & Chen, M. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1112.0442 · Cited by 1
A performance evaluation of optimal hybrid cache coherency protocols
Veenstra, J. E., & Fowler, R. J. (1992) · ACM SIGPLAN Notices · doi:10.1145/143371.143503 · Cited by 1
Methodical Competitive Snoopy-Caching
Nelson, G. (1990) · Springer eBooks · doi:10.1007/978-1-4612-4476-9_39 · Cited by 1
The optimal structure of algorithms for α -paging
Kovács, A., Meyer, U., Moruz, G., & Negoescu, A. (2015) · Information Processing Letters · doi:10.1016/j.ipl.2015.07.011
Enforcing cooperation and providing quality of service in wireless networks
Jimenez, J. C. Z., & José, J. (2010)
Parallel Computation Models — Some Useful Questions
Snir, M. (1989) · Springer eBooks · doi:10.1007/978-1-4613-9668-0_36
Epstein, L., van Stee, R., & Tamir, T. (2006) · Lecture notes in computer science · doi:10.1007/11785293_14
Online Vertex Cover and Matching: Beating the Greedy AlgorithmPreprint
Wang, Y., & Wong, S. C.-W. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1305.1694
“The ski rental problem was first studied in [20].”
BackgroundOnline problems and two-player games : algorithms and analysis
Sivadasan, N. (2004) · Max Planck Institute for Plasma Physics · doi:10.22028/d291-23760
“[KMRS88] proposed a new comparison measure called competitive analysis: compare the cost incurred by the online algorithm for serving to the cost of an”
BackgroundCombinatorial Online Optimization: Elevators & Yellow AngelsPreprint
Grötschel, M., Hiller, B., & Tuchscherer, A. (2007)
The Online Specialization Problem
Hong, E. S. (2006) · Discrete Mathematics & Theoretical Computer Science · doi:10.46298/dmtcs.359
“It was initially proposed as an analogue to the competitive snoopy caching problem Karlin et al. (1988).”
Multiplier with Parallel CSA using CRT’s Specific Moduli (2 k -1, 2 k , 2 k +1)
Kim, W. W., & Jang, S.-D. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-24709-8_23
Developing embedded software using compile-time virtualisation
Gray, I. (2010) · White Rose eTheses Online (University of Leeds, The University of Sheffield, University of York)
A New Competitive Analysis of Randomized Caching
Law, C., & Leiserson, C. E. (2000) · Lecture notes in computer science · doi:10.1007/3-540-40996-3_4
“Karlin et al. [ 15 ] proved that FWFk (Flush-When-Full) is also k=(k h + 1)-competitive with OPTh.”
BackgroundMohr, E. (2011) · Publications of the UdS (Saarland University) · doi:10.22028/d291-26157
MOO: A Methodology for Online Optimization through Mining the Offline OptimumPreprint
Lee, J. W. H., Tay, Y. C., & Tung, A. K. H. (2000) · arXiv (Cornell University) · doi:10.48550/arxiv.cs/0003072
Zhang, Y. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1504.05305
Engineering Efficient Paging Algorithms
Moruz, G., Negoescu, A., Neumann, C., & Weichert, V. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-30850-5_28
Rent or Buy Problems with a Fixed Time Horizon
Epstein, L., & Zebedat-Haider, H. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-40313-2_33
Competitive Ratio for Portfolio Management
Deng, X. (2001) · Encyclopedia of Optimization · doi:10.1007/0-306-48332-7_60
On Multi-threaded Metrical Task Systems
Feuerstein, E., Seiden, S. S., & de Loma, A. S. (2006) · Journal of Discrete Algorithms · doi:10.1016/j.jda.2005.12.005
“The term competitive analysis originates in [18].”
Power-aware online file allocation in mobile ad hoc networks
Mehler, J., & der Heide, F. M. A. (2009) · doi:10.1145/1583991.1584072
“snoopy caching [ 14 ], file replication [10], page migration [10], [3], [2], distributed paging and file allocation [4], [3], [2].”
BackgroundAdaptive memory coherence algorithms in DSVM
Zhou, J., Li, X., Dai, F., et al. (1994) · Journal of Computer Science and Technology · doi:10.1007/bf02943583
Adaptive algorithms for PASO systems
Westbrook, J., & Zuck, L. D. (1994) · ACM Symposium on Principles of Distributed Computing (PODC) · doi:10.1145/197917.198106
The Cost of Derandomization: Computability or Competitiveness
Deng, X., & Mahajan, S. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539791202301
On the On-Line Fuzzy Most Reliable Path Problem
Ma, W., Tang, S., & Wang, K. (2006) · International Conference on Machine Learning and Cybernetics · doi:10.1109/icmlc.2006.258610
Variations on the Theme of Caching
Gaşpar, C. (2005) · UWSpace (University of Waterloo)
Oyang, Y., & Wu, L.-C. (1992) · Proceedings of the ... Annual Hawaii International Conference on System Sciences/Proceedings of the Annual Hawaii International Conference on System Sciences · doi:10.1109/hicss.1992.183196
New utilization criteria for online scheduling
Hussein, M. E. (2005) · Technische Universität Dortmund Eldorado (Technische Universität Dortmund) · doi:10.17877/de290r-12516
Algorithmic Challenges in Green Data Centers
Lin, M. (2013) · doi:10.7907/nrxj-jb76
Competitive Analysis for the On-Line Fuzzy Most Connective Path Problem
Ma, W., Yu, Z.-F., & Wang, K. (2006) · International Conference on Machine Learning and Cybernetics · doi:10.1109/icmlc.2006.259048
Non-Additive Two-Option Ski Rental
Levi, A., & Patt-Shamir, B. (2013) · Lecture notes in computer science · doi:10.1007/978-3-319-03578-9_7
Feuerstein, E. (1995) · Lecture notes in computer science · doi:10.1007/3-540-59175-3_95
Engelberg, R., & Naor, J. S. (2016) · SIAM Journal on Computing · doi:10.1137/090760386
Joint Cache Partition and Job Assignment on Multi-Core Processors
Sackler, B. (2013)
Lower bounds for the multislope ski-rental problem
Fujiwara, H., Konno, Y., & Fujito, T. (2013) · International Symposium on Operations Research and its Applications in Engineering, Technology and Management (ISORA) · doi:10.1049/cp.2013.2252
“[7], where a matching lower and upper bound of 2 was derived.”
BackgroundInfluentialCompetitive Analysis for the Flat-Rate Problem
Fujiwara, H., Matsuda, A., & Fujito, T. (2016) · IEICE Transactions on Information and Systems · doi:10.1587/transinf.2015fcp0005
Albers, S. (2002)
OTIMIZANDO O ESCALONAMENTO DE JOBS NO PROCESSO DE RASTERIZAÇÃO DE DOCUMENTOS PERSONALIZÁVEIS
Pós-Graduação, P. D., & Computação, E. C. D. (2011)
SIGACT news online algorithms column 19
Chrobák, M. (2011) · ACM SIGACT News · doi:10.1145/1998037.1998057
SIGACT news online algorithms column 16
Chrobák, M. (2010) · ACM SIGACT News · doi:10.1145/1753171.1753194
Online-algorithms for reactive vehicle scheduling
Schmidt, G., & Jacob, E. (1995) · IFIP advances in information and communication technology · doi:10.1007/978-0-387-34928-2_5
A new competitive analysis of randomized caching (Extended Abstract)
Law, C., & Leiserson, C. E. (2007)
Online edge coloring of paths and trees with a fixed number of colors
Favrholdt, L. M., & Mikkelsen, J. W. (2016) · Acta Informatica · doi:10.1007/s00236-016-0283-0
“We measure the quality of an online algorithm, A , for Edge-k -Coloring using the standard notion of competitive ratio [12,16].”
MethodCompetitive algorithms for online matching and vertex cover problems
Wong, C. W. (2013) · DSpace@MIT (Massachusetts Institute of Technology)
“The classical ski-rental problem, which is first studied by Karlin et al. (1988), is a simplified version of our allocation-scheduling problem.”
BackgroundInfluentialRelative Worst-Order Analysis: A Survey
Boyar, J., Favrholdt, L. M., & Larsen, K. S. (2018) · Lecture notes in computer science · doi:10.1007/978-3-319-98355-4_13 · Cited by 3
Reducing Energy Consumption and Latency of Applications on Wireless Devices
Sehati, A. (2018) · Libraries and Cultural Resources (University of Calgary) · doi:10.11575/prism/13062
A New Approach to Competitive Analysis: Approximating the Optimal Competitive Ratio
Günther, E., Maurer, O., Megow, N., et al. (2012)
Handling Critical Jobs Online: Deadline Scheduling and Convex-Body Chasing
Schewior, K. (2018) · Operations research proceedings · doi:10.1007/978-3-319-89920-6_4
Tight Bounds for Restricted Grid Scheduling
Boyar, J., & Ellen, F. (2019) · International Journal of Foundations of Computer Science · doi:10.1142/s0129054119500102
Approximation Algorithms for Covering Problems
Koufogiannakis, C. (2009) · eScholarship (California Digital Library)
Tight Bounds for Restricted Grid SchedulingPreprint
Boyar, J., & Ellen, F. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1404.7325
“The competitive ratio [9, 7] of an on-line algorithm is the worst-case ratio of the on-line performance to the optimal off-line performance, up to an additive constant.”
BackgroundPeak-Aware Online Economic Dispatching for MicrogridsPreprint
Zhang, Y., Hajiesmaili, M., Cai, S., et al. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1508.03996
“Similar to the ski rental problem [12], the break-even point turns out to be the best balance between being aggressive and conservative.”
BackgroundThe Multi-shop Ski Rental ProblemPreprint
Ai, L., Wu, X., Huang, L., et al. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1404.2671
“[14], and then studied by Karlin’s seminal paper [13] which proposes a randomized algorithm and gives a e e−1 competitive ratio.”
BackgroundWeighted Online Problems with AdvicePreprint
Boyar, J., Favrholdt, L. M., Kudahl, C., et al. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1606.05210
“The quality of online algorithms is traditionally measured using the competitive ratio [12, 16], which is essentially the worst case ratio of the online performance to the performance of an optimal offline algorithm, i.”
BackgroundThe Frequent Items Problem in Online Streaming under Various Performance MeasuresPreprint
Boyar, J., Larsen, K. S., & Maiti, A. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1306.0771
“Competitive analysis [13, 12] evaluates an online algorithm in comparison with an optimal offline algorithm.”
MethodThe Advice Complexity of a Class of Hard Online ProblemsPreprint
Boyar, J., Favrholdt, L. M., Kudahl, C., et al. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1408.7033
“Definition 1 (Competitive ratio [23, 32] and advice complexity [7, 22]) The input to an online problem, P, is a request sequence σ = 〈r1, .”
BackgroundGuessing fractions of online sequences
Konrad, C., & Tonoyan, T. (2020) · Discrete Applied Mathematics · doi:10.1016/j.dam.2020.07.015
“Planning the replicas and transfers for other sites resembles a continuous version of the classical ski-rental problem [18] in that there is a trade-off”
BackgroundParking permit and network leasing problems
de Lima, M. S. (2018) · doi:10.47749/t/unicamp.2018.1014622
Risk-Reward Models for Two-Option Online Leasing Problem Under Sharing EconomyPreprint
Wu, J., & Zhang, Y. (2022) · SSRN Electronic Journal · doi:10.2139/ssrn.4087144
Manasse, M. S. (2014) · Springer eBooks · doi:10.1007/978-3-642-27848-8_378-2
Self-citationManasse, M. S. (2016) · Springer eBooks · doi:10.1007/978-1-4939-2864-4_378
Self-citationThe work function algorithm for the paging problem
Zhang, W., Hu, H., Cheng, Y., Li, H., & Wang, H. (2022) · Theoretical Computer Science · doi:10.1016/j.tcs.2022.07.014
Competitive Ratio for Portfolio Management
Deng, X. (2008) · Encyclopedia of Optimization · doi:10.1007/978-0-387-74759-0_74
Li, N., & Ma, R. (2023) · Parallel Processing Letters · doi:10.1142/s0129626423400030
Castenow, J., Feldkord, B., Hanselle, J., et al. (2022) · Lecture notes in computer science · doi:10.1007/978-3-031-21534-6_10
Algorithms for Big Data: DFG Priority Program 1736
Bast, H., Korzen, C., Meyer, U., & Penschuck, M. (2022) · Lecture notes in computer science · doi:10.1007/978-3-031-21534-6 · Cited by 4
Online $$\boldsymbol{L(2,1)}$$-Coloring Problem on Paths with Restricted Size of Memory
Bashirova, D. (2023) · Lobachevskii Journal of Mathematics · doi:10.1134/s1995080223020117
Introduction of Online Incentive Mechanism in Wireless Communications
Li, G., & Cai, J. (2024) · SpringerBriefs in computer science · doi:10.1007/978-3-031-58453-4_1
Competitive Analysis of Algorithms for an Online Distribution Problem
Barba, A., Bertazzi, L., & Golden, B. (2024) · Algorithms · doi:10.3390/a17060237
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.