The DOI matches its Crossref record; 13 of the 13 references it cites were found in a registry or an index.
Competitive snoopy caching
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 101–200 of 619
Methods for message routing in parallel machines
Leighton, T. (1992) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/129712.129721 · Cited by 60
Non-Clairvoyant Multiprocessor Scheduling of Jobs with Changing Execution Characteristics
Edmonds, J., Chinn, D. D., Brecht, T. B., & Deng, X. (2003) · Journal of Scheduling · doi:10.1023/a:1022952324290 · Cited by 57
“This measure was rst introduced in the study of a system memory management problem [10, 16, 23].”
MethodBoyar, J., Favrholdt, L. M., Kudahl, C., Larsen, K. S., & Mikkelsen, J. W. (2017) · ACM Computing Surveys · doi:10.1145/3056461 · Cited by 66
“There are various measures for the quality of online algorithms [Dorrigiv and L´opez-Ortiz 2005; Boyar et al. 2015b], but the most standard is the competitive ratio [Sleator and Tarjan 1985; Karlin et al. 1988], which is the online analog of the approximation ratio.”
Random walks on weighted graphs, and applications to on-line algorithms
Coppersmith, D., Doyle, P. G., Raghavan, P., & Snir, M. (1990) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/100216.100266 · Cited by 59
“1 Overview Much recent work has dealt with the competitive analysis of on-line algorithms [5, 16, 18].”
BackgroundDistributed Paging for General Networks
Awerbuch, B., Bartal, Y., & Fiat, A. (1998) · Journal of Algorithms · doi:10.1006/jagm.1998.0924 · Cited by 55
Karlin, A. R., Phillips, S. J., & Raghavan, P. (2000) · SIAM Journal on Computing · doi:10.1137/s0097539794268042 · Cited by 57
Self-citationStochastic Analyses for Online Combinatorial Optimization Problems
Garg, N., Gupta, A., Leonardi, S., et al. (2008) · Cited by 56
Patience is a Virtue: The Effect of Slack on Competitiveness for Admission Control
Goldwasser, M. H. (2003) · Journal of Scheduling · doi:10.1023/a:1022994010777 · Cited by 54
Routing and Admission Control in General Topology Networks
Gawlick, R., Kamath, A. P., Plotkin, S. A., et al. (1995) · Cited by 54
Greedy Δ-Approximation Algorithm for Covering with Arbitrary Constraints and Submodular Cost
Koufogiannakis, C., & Young, N. E. (2013) · Algorithmica · doi:10.1007/s00453-012-9629-3 · Cited by 53
“Examples include rent-or-buy [36,40], paging [23,43], weighted caching [2,14], connection caching [18], and file caching [3].”
BackgroundThe relative worst-order ratio applied to paging
Boyar, J., Favrholdt, L. M., & Larsen, K. S. (2007) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2007.03.001 · Cited by 48
“The standard measure for the quality of on-line algorithms is the competitive ratio [9, 12, 10 ], which is, roughly speaking, the worst-case ratio, over all possible input sequences, of the on-line performance to the optimal o-line performance.”
BackgroundRandomized and multipointer paging with locality of reference
Fiat, A., & Karlin, A. R. (1995) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/225058.225280 · Cited by 53
Self-citationNew results on server problems
Chrobák, M., Karloff, H. J., Payne, T., & Vishwanathan, S. (1990) · doi:10.5555/320176.320209 · Cited by 55
How Much Information about the Future Is Needed?
Dobrev, S., Kráľovič, R., & Pardubská, D. (2008) · Springer eBooks · doi:10.1007/978-3-540-77566-9_21 · Cited by 57
“[1], [4]). The standard measure used for evaluating online algorithms is the competitive ratio [ 16 ], [20], i.e.”
MethodKhosravi, A., Toosi, A. N., & Buyya, R. (2017) · Concurrency and Computation Practice and Experience · doi:10.1002/cpe.4125 · Cited by 51
“Our online algorithms are inspired by skirental problem [44].”
MethodCache coherence directories for scalable multiprocessors
Simoni, J. R. T. (1992) · Cited by 52
Divergence caching in client-server architectures
Huang, Y., Sloan, R. H., & Wolfson, O. (2002) · doi:10.1109/pdis.1994.331723 · Cited by 52
“[5, 11, 10 , 13]) have assumed a consistent environment, i.e.”
BackgroundPage Replacement with Multi-Size Pages and Applications to Web Caching
Irani, S. (2002) · Algorithmica · doi:10.1007/s00453-001-0125-4 · Cited by 49
Optimal prefetching and caching for parallel I/O sytems
Kallahalla, M., & Varman, P. (2001) · ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) · doi:10.1145/378580.378648 · Cited by 49
“In this section, we shall characterize the performance of online algorithms using the competitive ratio [14] as the metric.”
MethodCompetitive k-server algorithms
Fiat, A., Rabani, Y., & Ravid, Y. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/fscs.1990.89566 · Cited by 49
“[KMRS] later gave competitive algorithms for Snoopy Caching.”
MethodPreemptive scheduling of parallel jobs on multiprocessors
Deng, X., Gu, N., Brecht, T. B., & Lu, K. (1996) · doi:10.5555/313852.313912 · Cited by 47
Wang, G., & Zimmermann, R. (2014) · ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPATIAL GIS) · doi:10.1145/2666310.2666383 · Cited by 45
“and used in a communication minimization algorithm [11].”
BackgroundMethodSystem level online power management algorithms
Ramanathan, D., & Gupta, R. K. (2000) · Design, Automation, and Test in Europe · doi:10.1145/343647.343867 · Cited by 47
Online Algorithms for Rent-Or-Buy with Expert Advice.
Gollapudi, S., & Panigrahi, D. (2019) · International Conference on Machine Learning · Cited by 169
The value of consensus in online stochastic scheduling
Bent, R. W., & Hentenryck, P. V. (2004) · International Conference on Automated Planning and Scheduling · Cited by 54
On the Competitive Theory and Practice of Online List Accessing Algorithms
Bachrach, El-Yaniv, & Reinstädtler (2002) · Algorithmica · doi:10.1007/s00453-001-0069-8 · Cited by 43
“4 The term “competitive analysis” was coined by Karlin et al. [ 15 ].”
BackgroundOnline rescheduling of multiple picking agents for warehouse management
Rubrico, J. I. U., Higashi, T., Tamura, H., et al. (2010) · Robotics and Computer-Integrated Manufacturing · doi:10.1016/j.rcim.2010.06.011 · Cited by 43
Preemptive on-line scheduling for two uniform processors
Wen, J., & Du, D. (1998) · Operations Research Letters · doi:10.1016/s0167-6377(98)00032-7 · Cited by 43
Using prediction to accelerate coherence protocols
Mukherjee, S. S., & Hill, M. D. (2002) · Proceedings - International Symposium on Computer Architecture/Proceedings · doi:10.1109/isca.1998.694773 · Cited by 42
Ski rental with two general options
Lotker, Z., Patt-Shamir, B., & Rawitz, D. (2008) · Information Processing Letters · doi:10.1016/j.ipl.2008.07.009 · Cited by 43
“Abstract We define and solve a simple extension of the ski-rental problem [4].”
MethodInfluentialA decomposition theorem and bounds for randomized server problems
Blum, A. L., Karloff, H. J., Rabani, Y., & Saks, M. (1992) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1992.267772 · Cited by 42
“The measure of success used is the compeiitive ratio [ST, KMRS ]: roughly, this is the worst-case ratio of the cost charged to the algorithm on a request sequence, to the optimal offline cost of servicing that sequence (the optimal cost had it known the entire sequence in advance).”
MethodOnline Optimization: Competitive Analysis and Beyond
Krumke, S. O. (2002) · Cited by 41
Rent, Lease, or Buy: Randomized Algorithms for Multislope Ski Rental
Lotker, Z., Patt-Shamir, B., & Rawitz, D. (2012) · SIAM Journal on Discrete Mathematics · doi:10.1137/100794018 · Cited by 39
“tegy for any multislope instance by combining strategies for k classical instances. Specifically, what we do is as follows. Let pi be the e e−1-competitive profile for the ith (two slope) instance (see [10]). We define a profile ˆp for the multislope instance as follows: ˆpi(t) = pi 1(t)−pi+1 1 (t) for i ∈{1,...,k−1}, pˆ0…”
BackgroundMethodInfluentialJaillet, P., & Stafford, M. W. (2001) · Operations Research · doi:10.1287/opre.49.4.501.11227 · Cited by 40
Randomized Algorithms for Multiprocessor Page Migration
Westbrook, J. (1994) · SIAM Journal on Computing · doi:10.1137/s0097539791199796 · Cited by 39
Minimization of communication cost through caching in mobile environments
Sistla, A. P., Wolfson, O., & Huang, Y. (1998) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/71.667898 · Cited by 39
“8.2 Caching and Virtual Memory In the computer architecture and operating systems literature, there are studies of two subjects related to dynamic data allocation, namely, caching and distributed virtual memory (see [1], [3], [7], [8], [12], [15], [16], [19], [25], [ 29 ], [30], [27], [28], [31], [33], [38]).”
BackgroundInfluentialTCP dynamic acknowledgment delay (extended abstract)
Dooly, D. R., Goldman, S. A., & Scott, S. (1998) · doi:10.1145/276698.276792 · Cited by 38
Online traveling salesman problems with service flexibility
Jaillet, P., & Lu, X. (2011) · Networks · doi:10.1002/net.20454 · Cited by 38
“[18] introduce the notion of a competitive ratio.”
BackgroundCompetitive analysis of algorithms
Fiat, A., & Woeginger, G. J. (1998) · Lecture notes in computer science · doi:10.1007/bfb0029562 · Cited by 37
“The phrase competitive analysis itself was coined by Karlin, Manasse, Rudolph, and Sleator in their paper [8] on competitive snoopy caching.”
Base station scheduling of requests with fixed deadlines
Agarwal, M., & Puri, A. (2003) · Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM) · doi:10.1109/infcom.2002.1019293 · Cited by 37
Competitive algorithms for the weighted server problem
Fiat, A., & Ricklin, M. (1994) · Theoretical Computer Science · doi:10.1016/0304-3975(94)90154-6 · Cited by 38
Online Delay Management on a Single Train Line
Gatto, M., Jacob, R., Peeters, L. W. P., et al. (2007) · Springer eBooks · doi:10.1007/978-3-540-74247-0_17 · Cited by 36
“This online strategy is 2-competitive, as analyzed in [ KMRS88 ].”
MethodCombinatorial Online Optimization in Real Time
Grötschel, M., Krumke, S. O., Rambau, J., et al. (2001) · Springer eBooks · doi:10.1007/978-3-662-04331-8_33 · Cited by 36
Competitive algorithms for the dynamic selection of component implementations
Yellin, D. M. (2003) · IBM Systems Journal · doi:10.1147/sj.421.0085 · Cited by 36
Rent, Lease or Buy: Randomized Algorithms for Multislope Ski RentalPreprint
Lotker, Z., Patt-Shamir, B., & Rawitz, D. (2008) · arXiv (Cornell University) · Cited by 37
Online routing and scheduling of search-and-rescue teams
Shiri, D., Akbari, V., & Salman, F. S. (2020) · OR Spectrum · doi:10.1007/s00291-020-00594-w · Cited by 35
Page Migration Algorithms Using Work Functions
Chrobák, M., Larmore, L. L., Reingold, N., & Westbrook, J. (1997) · Journal of Algorithms · doi:10.1006/jagm.1996.0853 · Cited by 33
“Similar memory management problems are examined in [2, 5, 10, 11 , 12, 13, 15].”
BackgroundRandomized online interval scheduling
Seiden, S. S. (1998) · Operations Research Letters · doi:10.1016/s0167-6377(98)00019-4 · Cited by 33
Traversing Layered Graphs Using the Work Function Algorithm
Burley, W. R. (1996) · Journal of Algorithms · doi:10.1006/jagm.1996.0024 · Cited by 32
Comparing online algorithms for bin packing problems
Epstein, L., Favrholdt, L. M., & Kohrt, J. S. (2009) · Journal of Scheduling · doi:10.1007/s10951-009-0129-5 · Cited by 33
“Contrary to the competitive ratio (Graham 1966; Karlin et al. 1988), the relative worst-order ratio compares two online algorithms directly instead of using an intermediate comparison with an optimal offline algorithm.”
BackgroundCode transformations for energy-efficient device management
Heath, T., Pinheiro, E., Hom, J., et al. (2004) · IEEE Transactions on Computers · doi:10.1109/tc.2004.38 · Cited by 32
“argument about renting or buying skis [12].”
Latency effects of system level power management algorithms
Ramanathan, D., Irani, S., & Gupta, R. K. (2000) · doi:10.5555/602902.602982 · Cited by 32
A competitive dynamic data replication algorithm
Huang, Y., & Wolfson, O. (2002) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.1993.344051 · Cited by 31
“In the theoretical computer science community there has been work on online algorithms (e.g. [l]), particularly for paging (e.g. [l8]), Marching (e.g. [18]) and caching (e.g. [19]) .”
MethodSynchronization with multiprocessor caches
Lee, J., & Ramachandran, U. (1990) · ACM SIGARCH Computer Architecture News · doi:10.1145/325096.325107 · Cited by 32
Online File Caching with Rejection Penalties
Epstein, L., Imreh, C., Levin, A., & Nagy-György, J. (2013) · Algorithmica · doi:10.1007/s00453-013-9793-0 · Cited by 28
“A class of algorithms, called M ARKING A LGORITHMS , was later shown by Karlin et al. [27] to achieve the same bound.”
MethodAn optimal online algorithm for scheduling two machines with release times
Noga, J., & Seiden, S. S. (2001) · Theoretical Computer Science · doi:10.1016/s0304-3975(00)00264-4 · Cited by 30
“The term competitive analysis originated in [13].”
Distributed paging for general networks
Awerbuch, B., Bartal, Y., & Fiat, A. (1996) · Symposium on Discrete Algorithms · doi:10.5555/313852.314122 · Cited by 29
Online algorithms with advice: The tape model
Böckenhauer, H.-J., Komm, D., Kráľovič, R., Královič, R., & Mömke, T. (2017) · Information and Computation · doi:10.1016/j.ic.2017.03.001 · Cited by 29
Polylogarithmic Bounds on the Competitiveness of Min-cost Perfect Matching with Delays
Azar, Y., Chiplunkar, A., & Kaplan, H. Y. (2017) · ACM-SIAM Symposium on Discrete Algorithms (SODA) · doi:10.1137/1.9781611974782.67 · Cited by 30
Better Algorithms for Unfair Metrical Task Systems and Applications
Fiat, A., & Mendel, M. (2003) · SIAM Journal on Computing · doi:10.1137/s0097539700376159 · Cited by 29
Application transformations for energy and performance-aware device management
Heath, T., Pinheiro, E., Hom, J., et al. (2003) · International Conference on Parallel Architectures and Compilation Techniques · doi:10.1109/pact.2002.1106011 · Cited by 29
“The rationale for this assumption is similar to the famous competitive argument about renting or buying skis [11].”
BackgroundAn analysis of system level power management algorithms and their effects on latency
Ramanathan, D., Irani, S., & Gupta, R. K. (2002) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/43.986423 · Cited by 29
“However, the authors in [7] and [8] do not model service times in their analysis.”
BackgroundInfluentialApproximation in Preemptive Stochastic Online Scheduling
Megow, N., & Vredeveld, T. (2006) · Lecture notes in computer science · doi:10.1007/11841036_47 · Cited by 30
PC-OPT: optimal offline prefetching and caching for parallel I/O systems
Kallahalla, M., & Varman, P. (2002) · IEEE Transactions on Computers · doi:10.1109/tc.2002.1047757 · Cited by 28
“In this section, we shall characterize the online performance of PC-OPT using the competitive ratio [16] as the metric.”
MethodAn algorithm for dynamic data distribution
Wolfson, O., & Jajodia, S. (2003) · doi:10.1109/mrd.1992.242616 · Cited by 28
Competitive analysis of paging
Irani, S. (1998) · Lecture notes in computer science · doi:10.1007/bfb0029564 · Cited by 29
“This class was formally defined by Karlin, Manasse, Sleator, and Rudolph [ 19 ] and includes LRU.”
BackgroundHiding shared memory reference latency on the Galactica Net distributed shared memory architecture
Wilson, A. W., & LaRowe, R. P. (1992) · Journal of Parallel and Distributed Computing · doi:10.1016/0743-7315(92)90049-s · Cited by 28
“Update counters in the GIM mapping tables make it possible to use a competitive algorithm to make this decision [24].”
BackgroundMethodA Comparison of Performance Measures for Online Algorithms
Boyar, J., Irani, S., & Larsen, K. S. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-03367-4_11 · Cited by 27
Fully Distribution-Free Profit Maximization: The Inventory Management Case
Wagner, M. R. (2010) · Mathematics of Operations Research · doi:10.1287/moor.1100.0468 · Cited by 27
Fair versus Unrestricted Bin Packing
Azar, Y., Boyar, Favrholdt, L. M., et al. (2002) · Algorithmica · doi:10.1007/s00453-002-0965-6 · Cited by 27
A Decomposition Theorem for Task Systems and Bounds for Randomized Server Problems
Blum, A. L., Karloff, H. J., Rabani, Y., & Saks, M. (2000) · SIAM Journal on Computing · doi:10.1137/s0097539799351882 · Cited by 27
Two adaptive hybrid cache coherency protocols
Anderson, C., & Karlin, A. R. (2002) · Proceedings - International Symposium on High-Performance Computer Architecture/Proceedings · doi:10.1109/hpca.1996.501195 · Cited by 27
“Performance measurements across a range of parallel applications indicate that the adaptive protocols we present perform well compared to both Write-Invalidate and Write-Update protocols.”
MethodSelf-citationHardware assist for distributed shared memory
Wilson, A. W., LaRowe, R. P., & Teller, M. J. (2002) · IEEE International Conference on Distributed Computing Systems (ICDCS) · doi:10.1109/icdcs.1993.287702 · Cited by 27
Enabling Load Balancing for Lossless Datacenters
Hu, J., Zeng, C., Wang, Z., et al. (2023) · Proceedings/Proceedings - International Conference on Network Protocols · doi:10.1109/icnp59255.2023.10355615 · Cited by 26
“We use the classical rent-or-buy problem 1 with online decision-making [41] as the context of Proteus.”
MethodCompetitive analysis of the online inventory problem
Larsen, K. S., & Wøhlk, S. (2010) · European Journal of Operational Research · doi:10.1016/j.ejor.2010.05.019 · Cited by 26
Paging for multi-core shared caches
López-Ortíz, A., & Salinger, A. (2012) · doi:10.1145/2090236.2090246 · Cited by 25
“While in the latter setting any online marking algorithm has a bounded competitive ratio of K K−h+1 when the offline has a cache of size h ≤ K [27, 39], in multi-core paging the competitive ratio of traditional algorithms such as LRU, FIFO, CLOCK, and FWF can be arbitrarily large.”
BackgroundUnfair Problems and Randomized Algorithms for Metrical Task Systems
Seiden, S. (1999) · Information and Computation · doi:10.1006/inco.1998.2744 · Cited by 28
“Preliminaries”
Preemptive Scheduling of Parallel Jobs on Multiprocessors
Deng, X., Gu, N., Brecht, T. B., & Lu, K. (2000) · SIAM Journal on Computing · doi:10.1137/s0097539797315598 · Cited by 24
The distributed k-server problem-a competitive distributed translator for k-server algorithms
Bartal, Y., & Rosen, A. (1992) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1992.267756 · Cited by 25
“[ KMRS , ST]) to distributed ones, by choosing a leader that will run the global-control algorithm, while ignoring requests on covered points; for the case of k = n - 1, one can use the algorithm of [BLS] for metrical task systems which defines a fixed traversal sequence for the single point which is uncovered at any…”
MethodThe Relative Worst Order Ratio for On-Line Algorithms
Boyar, J., & Favrholdt, L. M. (2003) · Lecture notes in computer science · doi:10.1007/3-540-44849-7_13 · Cited by 26
“The results we obtain using the relative worst order ratio are compared to the standard competitive ratio [Graham 1966; Sleator and Tarjan 1985; Karlin et al. 1988 ] and to the competitive ratio on accommodating sequences [Boyar et al. 2001].”
BackgroundResultHeat and Dump: competitive distributed paging
Awerbuch, B., Bartal, Y., & Fiat, A. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1993.366885 · Cited by 24
Admission Control with Immediate Notification
Goldwasser, M. H., & Kerbikov, B. (2003) · Journal of Scheduling · doi:10.1023/a:1022956425198 · Cited by 24
Competitive Online Optimization under Inventory Constraints
Lin, Q., Yi, H., Pang, J. Z. F., Chen, M., Wierman, A., Honig, M. L., & Xiao, Y. (2019) · ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS) · doi:10.1145/3309697.3331495 · Cited by 23
“Well-known problems in the online optimization paradigm include the classic secretary problem [20], the ski rental problem [36], the one-way trading problem [23], and the k-server problem [27].”
BackgroundMethodA performance evaluation of optimal hybrid cache coherency protocols
Veenstra, J. E., & Fowler, R. J. (1992) · International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS) · doi:10.1145/143365.143503 · Cited by 24
“[29] proposed a competitive snoopy caching algorithm that uses write-update and switches to writeinvalidate when the cumulative cost of sending updates to processors having a copy of the data that they are not using equals the cost that would be incurred if they had to reread the data.”
MethodOn multiprocessor system scheduling
Deng, X., & Dymond, P. W. (1996) · ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) · doi:10.1145/237502.237510 · Cited by 24
“The competitive analysis of algorithms is a method of evaluating the performance of algorithms operating under imperfect information, rst introduced in the study of a system memory management problem [25][11][19].”
MethodFast and effective distribution-key recommendation for amazon redshift
Parchas, P., Naamad, Y., Bouwel, P. V., Faloutsos, C., & Petropoulos, M. (2020) · Proceedings of the VLDB Endowment · doi:10.14778/3407790.3407834 · Cited by 35
“…due to a possible change of architecture), the decision of whether or not to redistribute can be cast as an instance of the Ski Rental Problem [15, 27] (or related problems such as the Parking Permit Prob-lem [18]), and therefore analyzed in the lens of competitive analysis, which is out of…”
BackgroundKoufogiannakis, C., & Young, N. E. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-02927-1_53 · Cited by 21
“tes (without details) that their CIP-01 result extends CIP-UP, but it is not clear how (see [54, 55]). 3 online problem competitive ratio deterministic online comment SKI RENTAL 2; e e 1 det.; random [39, 47] ? PAGING k= potential function [59, 56] e.g. LRU, FIFO, FWF, Harmonic ? CONNECTION CACHING O(k) reduction to p…”
BackgroundBetter algorithms for unfair metrical task systems and applications
Fiat, A., & Mendel, M. (2000) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/335305.335408 · Cited by 23
“line algorithm A for a UMTS is a probability distribution over deterministic online algorithms. The expected cost of a randomized algorithm A on a sequence σ is denoted by E[costA(σ)]. Definition 2.1. [20, 15, 7] A randomized online algorithm A is called r competitive against an oblivious adversary if there exists some…”
BackgroundInfluentialThe CNN problem and other k-server variants
Koutsoupias, E., & Taylor, D. S. (2004) · Theoretical Computer Science · doi:10.1016/j.tcs.2004.06.002 · Cited by 23
“In this work, we use competitive analysis [5, 17, 24] to evaluate the quality of on-line algorithms; the competitive ratio is de ned to be the worst-case performance of the on-line algorithm, compared to the optimal cost for the same sequence of requests.”
MethodOptimal read-once parallel disk scheduling
Kallahalla, M., & Varman, P. (1999) · doi:10.1145/301816.301835 · Cited by 23
The Relative Worst Order Ratio Applied to Seat Reservation
Boyar, J., & Medvedev, P. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-27810-8_9 · Cited by 23
A competitive 3-server algorithm
Berman, P., Karloff, H. J., & Tardos, G. (1990) · Symposium on Discrete Algorithms · doi:10.5555/320176.320208 · Cited by 24
Simple and effective dynamic provisioning for power-proportional data centers
Lu, T., & Chen, M. (2012) · Conference on Information Sciences and Systems · doi:10.1109/ciss.2012.6310753 · Cited by 22
Routing and Admission Control in General Topology Networks with Poisson Arrivals
Kamath, A. P., Palmon, O., & Plotkin, S. A. (1998) · Journal of Algorithms · doi:10.1006/jagm.1997.0923 · Cited by 22
The relative worst order ratio applied to seat reservation
Boyar, J., & Medvedev, P. (2008) · ACM Transactions on Algorithms · doi:10.1145/1383369.1383379 · Cited by 22
Competitive Analysis of Network Load Balancing
Deng, X., Hai-ning, L., Long, J., et al. (1997) · Journal of Parallel and Distributed Computing · doi:10.1006/jpdc.1996.1257 · Cited by 22
Object allocation in distributed databases and mobile computers
Huang, Y., & Wolfson, O. (2002) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.1994.283007 · Cited by 22
Paging and list update under bijective analysis
Angelopoulos, S., & Schweitzer, P. (2009) · doi:10.5555/1496770.1496893 · Cited by 21
The Frequent Items Problem in Online Streaming Under Various Performance Measures
Boyar, J., Larsen, K. S., & Maiti, A. (2015) · International Journal of Foundations of Computer Science · doi:10.1142/s0129054115500239 · Cited by 21
“Competitive analysis [13, 12] evaluates an online algorithm in comparison with an optimal offline algorithm.”
MethodTheoretical Evidence for the Superiority of LRU-2 over LRU for the Paging Problem
Boyar, J., Ehmsen, M. R., & Larsen, K. S. (2007) · Lecture notes in computer science · doi:10.1007/11970125_8 · Cited by 21
“Let A(I) denote the number of page faults A has on request sequence I .T he standard measure for the quality of on-line algorithms is the competitive ratio: CR(A )o fA is CR(A )=i nf{c |∃ b : ∀I : A(I) ≤ c · OPT(I )+ b} , where OPT denotes an optimal off-line algorithm [ 9 ,13].”
Background
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.