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 301–400 of 619
Methods for message routing in parallel machines
Leighton, T. (1994) · Theoretical Computer Science · doi:10.1016/0304-3975(94)90163-5 · Cited by 10
Online algorithms for the multi-vehicle inventory-routing problem with real-time demands
Bertazzi, L., Chagas, G. O., Coelho, L. C., et al. (2024) · Transportation Research Part C Emerging Technologies · doi:10.1016/j.trc.2024.104892 · Cited by 9
“After that, Karlin et al. [43] introduced the concept of competitive analysis .”
BackgroundAn adaptive cache coherence protocol for chip multiprocessors
Kayi, A., & El‐Ghazawi, T. (2010) · doi:10.1145/1882453.1882458 · Cited by 9
“The selection of the cache coherence write policy on shared data, write-invalidate versus write-update, has been the main focus of many earlier studies [ 29 , 20, 51, 45, 22, 21, 33, 12, 50, 47].”
ResultRelaxing the Irrevocability Requirement for Online Graph Algorithms
Boyar, J., Favrholdt, L. M., Kotrbčı́k, M., et al. (2022) · Algorithmica · doi:10.1007/s00453-022-00944-w · Cited by 9
“y time. Competitiveanalysis For each graph problem, we study online algorithms in the standard, Late Accept, Late Reject, and Late Accept/Reject models using the standard tool of competitive analysis [25,17], where the performance of an online algorithm is compared to the optimum algorithm Opt via the competitive rati…”
MethodProbabilistic alternatives for competitive analysis
Hiller, B., & Vredeveld, T. (2011) · Computer Science - Research and Development · doi:10.1007/s00450-011-0149-1 · Cited by 12
“[30].”
Risk–reward models for on-line leasing of depreciable equipment
Zhang, Y., Zhang, W., Xu, W., et al. (2011) · Computers & Mathematics with Applications · doi:10.1016/j.camwa.2011.11.005 · Cited by 9
Martin, M. M. K., Harper, P. J., Sorin, D. J., et al. (2003) · ACM SIGARCH Computer Architecture News · doi:10.1145/871656.859642 · Cited by 9
On-Line Algorithms for a Single Machine Scheduling Problem
Mao, W., Kincaid, R. K., & Rifkin, A. (1995) · Operations research, computer science. Interface series · doi:10.1007/978-1-4615-2223-2_8 · Cited by 9
On-line algorithms for 2-coloring hypergraphs via chip games
Aslam, J., & Dhagat, A. (1993) · Theoretical Computer Science · doi:10.1016/0304-3975(93)90025-o · Cited by 9
ON THE k-TRUCK SCHEDULING PROBLEM
Ma, W., Xu, Y., You, J., et al. (2004) · International Journal of Foundations of Computer Science · doi:10.1142/s0129054104002340 · Cited by 9
SIGACT news online algorithms column 17
Chrobák, M. (2010) · ACM SIGACT News · doi:10.1145/1907450.1907547 · Cited by 10
Better Bounds on Online Unit Clustering
Ehmsen, M. R., & Larsen, K. S. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-13731-0_35 · Cited by 8
EXPLORING AN UNKNOWN GRAPH (Extended Abstract)
Deng, X., & Papadimitriou, C. H. (1990) · Cited by 8
Relaxing the Irrevocability Requirement for Online Graph Algorithms
Boyar, J., Favrholdt, L. M., Kotrbčı́k, M., et al. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-62127-2_19 · Cited by 8
Competitive Analysis for the 3-Slope Ski-Rental Problem with the Discount Rate
Fujiwara, H., Satou, S., & Fujito, T. (2016) · IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences · doi:10.1587/transfun.e99.a.1075 · Cited by 8
Paging and List Update under Bijective Analysis
Angelopoulos, S., & Schweitzer, P. (2009) · ACM-SIAM Symposium on Discrete Algorithms (SODA) · doi:10.1137/1.9781611973068.123 · Cited by 8
Models and Algorithms for Stochastic Online Scheduling
Megow, N., Uetz, M., & Vredeveld, T. (2006) · Mathematics of Operations Research · doi:10.1287/moor.1060.0201 · Cited by 8
On-Line Deadline Scheduling on Multiple Resources
Kim, J., & Chwa, K. (2001) · Lecture notes in computer science · doi:10.1007/3-540-44679-6_50 · Cited by 8
On the value of information in coordination games
Irani, S., & Rabani, Y. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1993.366886 · Cited by 8
Towards a theory of cost management for digital libraries and electronic commerce
Sistla, A. P., Wolfson, O., Yesha, Y., & Sloan, R. H. (1998) · ACM Transactions on Database Systems · doi:10.1145/296854.277641 · Cited by 8
“More specifically, we use the notion of competitiveness (see Karlin et al. [1988]) of online algorithms.”
MethodOnline paging and file caching with expiration times
Kimbrel, T. (2001) · Theoretical Computer Science · doi:10.1016/s0304-3975(00)00263-2 · Cited by 8
Using Prediction to Accelerate Coherence
Mukherjee, S. S., & Hill, M. D. (1998) · Cited by 8
Online Bounded AnalysisPreprint
Boyar, J., Epstein, L., Favrholdt, L. M., et al. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1602.06708 · Cited by 8
“Competitive analysis (Sleator and Tarjan 1985; Karlin et al. 1988) is the most common tool for comparing online algorithms.”
MethodOnlineMin: A Fast Strongly Competitive Randomized Paging Algorithm
Brodal, G. S., Moruz, G., & Negoescu, A. (2012) · Theory of Computing Systems · doi:10.1007/s00224-012-9427-y · Cited by 7
“This measure, denoted competitive ratio [15, 19], states that an online algorithm A has competitive ratio c if for any input sequence its cost satisfies cost(A) ≤ c · cost(OPT) + b, where cost(OPT) is the cost of an optimal offline algorithm and b is a constant.”
BackgroundRelative Interval Analysis of Paging Algorithms on Access Graphs
Boyar, J., Gupta, S., & Larsen, K. S. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-40104-6_17 · Cited by 7
Optimal Online Edge Coloring of Planar Graphs with Advice
Mikkelsen, J. W. (2015) · Lecture notes in computer science · doi:10.1007/978-3-319-18173-8_26 · Cited by 7
Competitive algorithms for the on-line inventory problem
Ma, W., & Chen, G. (2005) · doi:10.1109/icmlc.2004.1382313 · Cited by 7
“However, problem ( 2 ) is very difficult for the decision-maker as he does not know the quantity of buyers in advance.”
BackgroundInfluentialOnline traveling salesman problem with deadlines and service flexibility
Wen, X., Xu, Y., & Zhang, H. (2013) · Journal of Combinatorial Optimization · doi:10.1007/s10878-013-9654-4 · Cited by 7
“The worst-case ratio of online and offline costs is called competitive ratio, which is used to evaluate the performance of the online algorithms (Karlin et al. 1988).”
MethodCOMPETITIVE ANALYSIS FOR THE MOST RELIABLE PATH PROBLEM WITH ONLINE AND FUZZY UNCERTAINTIES
Ma, W., Tang, S., & Wang, K. (2008) · International Journal of Pattern Recognition and Artificial Intelligence · doi:10.1142/s0218001408006156 · Cited by 7
Suryanarayanan, V., Minson, R., & Theodoropoulus, G. K. (2009) · IEEE/ACM International Symposium on Distributed Simulation and Real Time Applications (DS-RT) · doi:10.1109/ds-rt.2009.31 · Cited by 7
Scheduling light-trails on WDM rings
Pal, S., & Ranade, A. (2012) · Journal of Parallel and Distributed Computing · doi:10.1016/j.jpdc.2012.05.010 · Cited by 7
“For the online problem, we use the notion of competitive analysis [2], [3], [4].”
MethodBounds for Scheduling Jobs on Grid Processors
Boyar, J., & Ellen, F. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-40273-9_2 · Cited by 7
SIGACT news online algorithms column 1
Chrobák, M. (2003) · ACM SIGACT News · doi:10.1145/954092.954104 · Cited by 10
“It has been now 16 years since the term “competitive online algorithm” appeared in the literature for the first time [ 10 ].”
BackgroundA Better bound of randomized algorithms for the multislope ski-rental problem
Hu, M., & Xu, W. (2017) · RAIRO - Theoretical Informatics and Applications · doi:10.1051/ita/2017009 · Cited by 9
“This problem in continuous time case is discussed by Karlin et al. [5, 6] as following.”
BackgroundSAL-Hashing: A Self-Adaptive Linear Hashing Index for SSDs
Jin, P., Yang, C., Wang, X., et al. (2018) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2018.2884714 · Cited by 7
The Maximum Resource Bin Packing Problem
Boyar, J., Epstein, L., Favrholdt, L. M., et al. (2005) · Lecture notes in computer science · doi:10.1007/11537311_35 · Cited by 7
Eliminating Useless Messages in Write-Update Protocols on Scalable Multiprocessors
Bianchini, R., LeBlanc, T. J., & Veenstra, J. E. (1994) · Cited by 7
Uniform service systems with k servers
Feuerstein, E. (1998) · Lecture notes in computer science · doi:10.1007/bfb0054307 · Cited by 7
“On-line algorithms are in general evaluated using competitive analysis [11]: an on-line algorithm for a certain problem is said to be c-competitive if the cost incurred by it to serve any input is at most c times the cost charged to the optimal (off-line) algorithm for tha t input plus a constant.”
MethodThe weighted list update problem and the lazy adversary
d’Amore, F., Marchetti-Spaccamela, A., & Nanni, U. (1993) · Theoretical Computer Science · doi:10.1016/0304-3975(93)90201-4 · Cited by 7
Empirical investigation of the Markov reference model
Liberatore, V. (1999) · Symposium on Discrete Algorithms · Cited by 7
Connection caching: model and algorithms
Cohen, E., Kaplan, H. Y., & Zwick, U. (2003) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(03)00041-2 · Cited by 7
“Algorithm FWF3 does not require additional communication for unmarkings, since they are communicated by connection closures.”
MethodInfluentialAdmission control and routing: theory and practice
Gawlick, R., Lynch, N. A., & Clark, D. D. (1995) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 7
Online Multicommodity Routing with Time Windows
Harks, T., Heinz, S., Pfetsch, M. E., et al. (2007) · OPUS (Augsburg University) · Cited by 7
A New Method for Computing Page-Fault Rates
Chu, J.-H., & Knott, G. D. (1993) · SIAM Journal on Computing · doi:10.1137/0222079 · Cited by 7
On algorithm design for metrical task systems
Burley, W. R., & Irani, S. (1995) · Symposium on Discrete Algorithms · doi:10.5555/313651.313779 · Cited by 7
Randomization can be as helpful as a glimpse of the future in online computationPreprint
Mikkelsen, J. W. (2015) · arXiv (Cornell University) · doi:10.4230/lipics.esa.2016.37 · Cited by 7
Evaluating the impact of coherence protocols on parallel logic programming systems.
Costa, V. S., Bianchini, R., & Dutra, I. (1997) · Cited by 7
Online multi-coloring with advice
Christ, M. G., Favrholdt, L. M., & Larsen, K. S. (2015) · Theoretical Computer Science · doi:10.1016/j.tcs.2015.06.044 · Cited by 6
“r of colors used by A on the input sequence I. When I is clear from the context, we simply write A instead of A(I). The quality of an online algorithm is often given in terms of the competitive ratio [35, 26]. An online multi-coloring algorithm is c-competitiveif there exists a constant α such that for all input seque…”
MethodA New Approach to Capacity Scaling Augmented with Unreliable Machine Learning Predictions
Rutten, D., & Mukherjee, D. (2023) · Mathematics of Operations Research · doi:10.1287/moor.2023.1364 · Cited by 5
“The constant β/θ is the default choice if ω = ∞ and is used in popular state-of-the art approaches [5, 27, 29, 34].”
BackgroundHe, X., Xiang, J., Xiao, J., Cheng, T. C. E., & Tian, Y. (2022) · Computers & Operations Research · doi:10.1016/j.cor.2022.105991 · Cited by 8
Data structures and terminating Petri nets
Sleator, D. D. (2005) · Springer eBooks · doi:10.1007/bfb0023850 · Cited by 6
Self-citationOn Multicriteria Online Problems
Flammini, M., & Nicosia, G. (2000) · Lecture notes in computer science · doi:10.1007/3-540-45253-2_18 · Cited by 6
“Definition 1. [ 11 ,21] A is said c-competitive if, for all possible sequences σ, cost(A, σ )= i cost(A, ri) ≤ c · opt(σ )+ α ,w hereopt(σ) is the cost paid to serve σ by an optimal offline algorithm that knows all the sequence σ in advance and α is a suitable constant independent from the length m of σ.”
BackgroundAsymptotically Optimal Online Page Migration on Three Points
Matsubayashi, A. (2013) · Algorithmica · doi:10.1007/s00453-013-9841-9 · Cited by 6
“These algorithms are optimal because the deterministic lower bound is 3 for every network with at least two nodes [8, 11].”
BackgroundFilippini, F., Lattuada, M., Ciavotta, M., Jahani, A., Ardagna, D., & Amaldi, E. (2022) · IEEE Transactions on Services Computing · doi:10.1109/tsc.2022.3188440 · Cited by 9
“However, the problems considered, while having some features in common with the one addressed in this paper, are considerably simpler and thus more suitable to be analyzed with the tool of competitive analysis [40].”
MethodEfficient offline algorithms for the bicriteria k-server problem and online applications
Flammini, M., Navarra, A., & Nicosia, G. (2006) · Journal of Discrete Algorithms · doi:10.1016/j.jda.2005.12.006 · Cited by 6
“Roughly speaking, the maximum ratio between their respective performances, taken over all the possible sequences, is denoted as the competitive ratio [7,15].”
BackgroundAn Online Algorithm Optimally Self-tuning to Congestion for Power Management Problems
Bein, W. W., Hatta, N., Hernandez-Cons, N., Ito, H., Kasahara, S., & Kawahara, J. I. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-29116-6_4 · Cited by 6
“An optimal online algorithm is well known for this problem in the context of the worst case competitive analysis [7,11,12].”
BackgroundClient-Server Caching with Expiration Timestamps
Carpenter, T. J., Carter, R., Cochinwala, M., & Eiger, M. I. (2001) · Distributed and Parallel Databases · doi:10.1023/a:1019248721089 · Cited by 8
“No item can remain for more than k (where k is the cache size) faults after its expiration [ 15 ].”
BackgroundThe Accomodating Function — A Generalization of the Competitive Ratio
Boyar, J., Larsen, K. S., & Nielsen, M. N. (1999) · Lecture notes in computer science · doi:10.1007/3-540-48447-7_9 · Cited by 6
“The competitive ratio [17, 29, 23], as a measure for the quality of on-line algorithms, has been criticized for giving bounds that are unrealistically pessimistic [5, 7, 18, 22, 25] and for not being able to distinguish between algorithms with very different behavior in practical applications [7, 18, 25, 28].”
BackgroundOn-line scheduling with hard deadlines
Goldman, S. A., Parwatikar, J., & Suri, S. (1997) · Lecture notes in computer science · doi:10.1007/3-540-63307-3_65 · Cited by 6
“We use standard competitive analysis [12, 10, 6] to evaluate our algorithms.”
MethodOn the Value of Coordination in Distributed Decision Making
Irani, S., & Rabani, Y. (1996) · SIAM Journal on Computing · doi:10.1137/s0097539794261428 · Cited by 6
“However, part of the reason for the recent interest in this area is the introduction of an appealing means of evaluating on-line algorithms called competitive analysis [18, 15].”
BackgroundA new variable-sized bin packing problem
Boyar, J., & Favrholdt, L. M. (2010) · Journal of Scheduling · doi:10.1007/s10951-010-0199-4 · Cited by 6
“The standard measure for the quality of on-line algorithms is the competitive ratio (Sleator and Tarjan 1985; Karlin et al. 1988), which is the worst-case ratio of the on-line performance to the optimal off-line performance, up to an additive constant.”
BackgroundFiat, A., Mendel, M., & Seiden, S. S. (2002) · Lecture notes in computer science · doi:10.1007/3-540-45749-6_45 · Cited by 6
Feuerstein, E., & de Loma, A. S. (1996) · Lecture notes in computer science · doi:10.1007/bfb0009518 · Cited by 6
“2 The Algorithms All the algorithms presented in this paper for the di erent versions of MTP are based in Flush-When-Full (FWF), a very well known k-competitive on-line algorithm for Paging, that was introduced in [Karlin et al. 1988].”
MethodOn-line resource management with applications to routing and scheduling
Leonardi, S., & Marchetti-Spaccamela, A. (1995) · Lecture notes in computer science · doi:10.1007/3-540-60084-1_83 · Cited by 6
Faster Streaming algorithms for graph spannersPreprint
Baswana, S. (2006) · arXiv (Cornell University) · doi:10.48550/arxiv.cs/0611023 · Cited by 6
“ng memory. It is due to this restriction that the streaming model is more stringent than other models namely, various external memory models [1, 30], and models for competitive analysis of algorithms [23]. The features and restrictions of the streaming model have been motivated by various technological factors pertain…”
BackgroundOnline algorithms for page replication in rings
Głazek, W. (2001) · Theoretical Computer Science · doi:10.1016/s0304-3975(00)00262-0 · Cited by 8
Lower and Upper Bounds for the Problem of Page Replication in Ring Networks
Głazek, W. (1999) · Lecture notes in computer science · doi:10.1007/3-540-48340-3_25 · Cited by 6
Fast Classical and Quantum Algorithms for Online $k$-server Problem on TreesPreprint
Kapralov, R., Khadiev, K. R., Mokut, J., Shen, Y., & Yagafarov, M. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2008.00270 · Cited by 20
“The most standard method to define the effectiveness of an online algorithm is the competitive ratio [27,20].”
MethodCompetitive-Ratio Approximation Schemes for Makespan Scheduling Problems
Kurpisz, A., Mastrolilli, M., & Stamoulis, G. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-38016-7_14 · Cited by 5
Online multi-coloring on the path revisited
Christ, M. G., Favrholdt, L. M., & Larsen, K. S. (2013) · Acta Informatica · doi:10.1007/s00236-013-0184-4 · Cited by 5
“We follow the tradition from the area of approximation algorithms and measure the performance of an online algorithm using competitive analysis [1,6,10,11], comparing the algorithm’s performance to that of an optimal offline algorithm.”
InfluentialBoyar, J., Epstein, L., Favrholdt, L. M., et al. (2016) · Lecture notes in computer science · doi:10.1007/978-3-319-34171-2_10 · Cited by 5
Weighted Online Problems with Advice
Boyar, J., Favrholdt, L. M., Kudahl, C., et al. (2016) · Lecture notes in computer science · doi:10.1007/978-3-319-44543-4_14 · Cited by 5
Competitive regularised regression
Jamil, W., & Bouchachia, A. (2019) · Neurocomputing · doi:10.1016/j.neucom.2019.08.094 · Cited by 5
“The thought of comparing the best offline algorithm to online algorithms originated from [17] and the term “competitive analysis” was first used by [18].”
MethodAnalysis of Lower Bounds for the Multislope Ski-Rental Problem
Fujiwara, H., KONNO, Y., & Fujito, T. (2014) · IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences · doi:10.1587/transfun.e97.a.1200 · Cited by 5
“[7], where a matching lower and upper bound of 2 was derived.”
BackgroundInfluentialOnline algorithms for locating checkpoints
Bern, M. W., Greene, D., Raghunathan, A. U., et al. (1990) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/100216.100264 · Cited by 5
“We analyze the competitiveness of our algorithms [3, 9, 11, 13].”
MethodOn-line algorithms for locating checkpoints
Bern, M. W., Greene, D., Raghunathan, A. U., et al. (1994) · Algorithmica · doi:10.1007/bf01294262 · Cited by 5
“The player’s total work before the adversary must reset at m/2 is at least m4/3, so over an entire “superepoch” the player’s ratio can be no better than m1/3/2− 1.”
BackgroundStochastization of Weighted Automata
Avni, G., & Kupferman, O. (2015) · Lecture notes in computer science · doi:10.1007/978-3-662-48057-1_7 · Cited by 6
“The optimal deterministic online algorithm is due to [19]; rent skis forM−1 consecutive days, and buy skis on theM -th day, assuming skiing continues.”
BackgroundInvalidate or Update? Revisiting Coherence for Tomorrow's Cache Hierarchies
Zhu, M., Shahab, A., Katsarakis, A., et al. (2021) · International Conference on Parallel Architectures and Compilation Techniques · doi:10.1109/pact52795.2021.00024 · Cited by 5
“The CU protocol, derived from the competing snooping protocol [23], and extended to a directory-based implementation [24], associates a counter value with each cache block.”
Competitive Analysis for Online Leasing Problem with Compound Interest Rate
Yang, X., Zhang, W.-G., Xu, W., & Zhang, Y. (2011) · Abstract and Applied Analysis · doi:10.1155/2011/156254 · Cited by 5
Boyar, J., Epstein, L., Favrholdt, L. M., et al. (2017) · Journal of Scheduling · doi:10.1007/s10951-017-0536-y · Cited by 5
“Competitive analysis (Sleator and Tarjan 1985; Karlin et al. 1988) is the most common tool for comparing online algorithms.”
MethodOnline Algorithms for Multi-shop Ski Rental with Machine Learned Predictions
Wang, S., & Li, J. (2020) · Adaptive Agents and Multi-Agents Systems · doi:10.65109/ocnn5096 · Cited by 6
Randomized online multi-threaded paging
Seiden, S. S. (1998) · Lecture notes in computer science · doi:10.1007/bfb0054374 · Cited by 5
“The term competitive analysis originated in [9].”
Competitive analysis for the on-line fuzzy shortest path problem
Ma, W., & Chen, G. (2005) · International Conference on Machine Learning and Cybernetics · doi:10.1109/icmlc.2005.1527064 · Cited by 5
Coll, P. E., Durán, G., & Moscato, P. (1999) · McGraw-Hill Ltd., UK eBooks · Cited by 5
Weighted Online Problems with Advice
Boyar, J., Favrholdt, L. M., Kudahl, C., et al. (2017) · Theory of Computing Systems · doi:10.1007/s00224-017-9806-5 · Cited by 5
“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.”
BackgroundLogical Time Coherence Maintenance
de Supinski, B. R. (1998) · doi:10.18130/v3r28v · Cited by 5
Manasse, M. S. (2008) · Encyclopedia of Algorithms · Cited by 6
Self-citationCompetitive-Ratio Approximation Schemes for Minimizing the Makespan in the Online-List ModelPreprint
Megow, N., & Wiese, A. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1303.1912 · Cited by 5
Strategic directions in research in theory of computing
Loui, M. C. (1996) · ACM Computing Surveys · doi:10.1145/242223.242240 · Cited by 6
“One major 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 Papadimitriou 1994].”
BackgroundMore on weighted servers or FIFO is better than LRU
Epstein, L., Imreh, C., & van Stee, R. (2003) · Theoretical Computer Science · doi:10.1016/s0304-3975(03)00287-1 · Cited by 5
“The marking algorithms, which are defined in [9], unmark all the pages in the caches at the beginning of each phase.”
BackgroundHeuristics and Policies for Online Pickup and Delivery Problems
Aleksandrov, M. D. (2012) · New University of Lisbon's Repository (New University of Lisbon) · Cited by 5
Risk Management for Online Simplified Bahncard Problem
Xin, C., Cui, W., & Ma, W.-M. (2006) · International Conference on Machine Learning and Cybernetics · doi:10.1109/icmlc.2006.258441 · Cited by 6
“[4] coined the term competitive analysis.”
Analysis of buffer replacement policies for WWW proxy
Kim, I. H., Yeom, H. Y., & Lee, J. (2002) · International Conference on Information Networking · doi:10.1109/icoin.1998.648421 · Cited by 5
“Cache management has been extensively studied in areas such as le system and hardware cache memory [11],[2].”
BackgroundOptimal Algorithms for Ski Rental with Soft Machine-Learned PredictionsPreprint
Kodialam, R. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1903.00092 · Cited by 19
“The Ski Rental problem has various applications ranging from cloud server pricing to snoopy caching [4] - in many of these applications, predictive information is indeed available and thus our result provides a way to use this information while still preserving competitive guarantees.”
BackgroundLi, N., Ma, R., & Zhang, Y. (2025) · Journal of Combinatorial Optimization · doi:10.1007/s10878-025-01271-w · Cited by 4
“It is widely recognized that (Karlin et al. 1988) introduced the concept of competitive ratio, which serves as a common measure to assess the quality of online algorithms.”
List Factoring and Relative Worst Order Analysis
Ehmsen, M. R., Kohrt, J. S., & Larsen, K. S. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-18318-8_11 · Cited by 4
OnlineMin: A Fast Strongly Competitive Randomized Paging Algorithm
Brodal, G. S., Moruz, G., & Negoescu, A. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-29116-6_14 · Cited by 4
Relative interval analysis of paging algorithms on access graphs
Boyar, J., Gupta, S., & Larsen, K. S. (2014) · Theoretical Computer Science · doi:10.1016/j.tcs.2014.11.035 · Cited by 4
“The most standard measure of quality of an online algorithm, competitive analysis [17, 14], cannot directly distinguish between most of them.”
BackgroundA Cost Efficient Online Algorithm for Automotive Idling Reduction
Dong, C., Zeng, H., & Chen, M. (2014) · Proceedings - ACM IEEE Design Automation Conference · doi:10.1145/2593069.2593070 · Cited by 4
Bounds for the Multislope Ski-Rental Problem
Fujiwara, H., SHIBUSAWA, K., Yamamoto, K., & Yamamoto, H. (2020) · IEICE Transactions on Information and Systems · doi:10.1587/transinf.2019fcp0001 · Cited by 4
“Since a matching bound is already given for each of the cases of k ≤ 3 by [4] and [8], we consider only k ≥ 4 in the rest of this section.”
BackgroundInfluential
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.