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
Fiat, A., Karp, R. M., Luby, M., McGeoch, L. A., Sleator, D. D., & Young, N. E. (1991) · Journal of Algorithms · doi:10.1016/0196-6774(91)90041-v · Cited by 457
“Candidates include non-uniform server problems, maintaining a list [15], and snoopy caching [9].”
BackgroundMethodSelf-citationDynamic Right-Sizing for Power-Proportional Data Centers
Lin, M., Wierman, A., Andrew, & Thereska, E. (2013) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2012.2226216 · Cited by 446
“, to stop “renting” and to “buy”) is 2-competitive [38].”
Dynamic right-sizing for power-proportional data centers
Lin, M., Wierman, A., Andrew, L. L. H., & Thereska, E. (2011) · 2011 Proceedings IEEE INFOCOM · doi:10.1109/infcom.2011.5934885 · Cited by 437
Competitive algorithms for server problems
Manasse, M. S., McGeoch, L. A., & Sleator, D. D. (1990) · Journal of Algorithms · doi:10.1016/0196-6774(90)90003-w · Cited by 425
Self-citationHenzinger, M., Raghavan, P., & Rajagopalan, S. (1999) · DIMACS Series in Discrete Mathematics and Theoretical Computer Science · doi:10.1090/dimacs/050/05 · Cited by 418
“Our model appears at first sight to be closely related to paper s on I/O complexity [HK81], hierarchical memory [AACS87], paging [ST85] and competitive analysis [ KMRS88 ], as well as external memory algorithms [VV96].”
BackgroundLebeck, A. R., Fan, X., Zeng, H., & Ellis, C. (2000) · ACM SIGPLAN Notices · doi:10.1145/356989.356999 · Cited by 370
“A particularly valuable approach is based on the \ski rent-to-buy" problem formulation for competitive algorithms [22, 25].”
MethodCompetitive algorithms for on-line problems
Manasse, M., McGeoch, L., & Sleator, D. (1988) · Proceedings of the twentieth annual ACM symposium on Theory of computing - STOC '88 · doi:10.1145/62212.62243 · Cited by 358
Self-citationEnergy conservation techniques for disk array-based servers
Pinheiro, E., & Bianchini, R. (2004) · International Conference on Supercomputing · doi:10.1145/1006209.1006220 · Cited by 346
“The rationale for this definition is similar to the competitive argument about renting or buying skis [15].”
BackgroundOn-line routing of virtual circuits with applications to load balancing and machine scheduling
Aspnes, J., Azar, Y., Fiat, A., Plotkin, S., & Waarts, O. (1997) · Journal of the ACM · doi:10.1145/258128.258201 · Cited by 330
An optimal on-line algorithm for metrical task system
Borodin, A., Linial, N., & Saks, M. E. (1992) · Journal of the ACM · doi:10.1145/146585.146588 · Cited by 326
“u is a function only of the first i tasks T 1T z . co T’ and SO; that is, the tasks are received one at a time in order and the algorithm must output u(i) upon receiving T’. To measure the efficiency of an on-line algorithm A as compared to the optimal (off-line) algorithm, we say that A is w-competitive (after [ 15 ]…”
BackgroundInfluentialEnergy-Efficient Server Clusters
Elnozahy, E. N. M., Kistler, M., & Rajamony, R. (2002) · Cited by 281
Martin, M. M. K., Hill, M. D., & Wood, D. A. (2003) · Proceedings - International Symposium on Computer Architecture/Proceedings · doi:10.1145/859618.859640 · Cited by 275
Fine-grain access control for distributed shared memory
Schoinas, I., Falsafi, B., Lebeck, A. R., et al. (1994) · International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS) · doi:10.1145/195473.195575 · Cited by 269
“While custom hardware performs an action quickly, research has shown that no single protocol is optimal for all applications [ 16 ] or even for all data structures within an application [3, 12].”
BackgroundOn the power of randomization in on-line algorithms
Ben-David, S., Borodin, A., Karp, R., Tardos, G., & Wigderson, A. (1994) · Algorithmica · doi:10.1007/bf01294260 · Cited by 262
Competitive randomized algorithms for nonuniform problems
Karlin, A. R., Manasse, M. S., McGeoch, L. A., & Owicki, S. (1994) · Algorithmica · doi:10.1007/bf01189993 · Cited by 258
“Thus the deterministic algorithm of Karlin et al. [ 14 ] is also optimally competitive against this adversary.”
MethodInfluentialSelf-citationFirefly: a multiprocessor workstation
Thacker, C. P., & Stewart, L. (1987) · ACM SIGOPS Operating Systems Review · doi:10.1145/36204.36199 · Cited by 235
Optimal Search and One-Way Trading Online Algorithms
El-Yaniv, R., Fiat, A., Karp, R. M., & Turpin, G. (2001) · Algorithmica · doi:10.1007/s00453-001-0003-0 · Cited by 210
“[21].”
New Ressults on Server Problems
Chrobak, M., Karloof, H., Payne, T., & Vishwnathan, S. (1991) · SIAM Journal on Discrete Mathematics · doi:10.1137/0404017 · Cited by 208
Scheduling Parallel Machines On-Line
Shmoys, D. B., Wein, J., & Williamson, D. P. (1995) · SIAM Journal on Computing · doi:10.1137/s0097539793248317 · Cited by 207
An optimization-driven dynamic vehicle routing algorithm for on-demand meal delivery using drones
Liu, Y. (2019) · Computers & Operations Research · doi:10.1016/j.cor.2019.05.024 · Cited by 202
Koren, G., & Shasha, D. (1995) · SIAM Journal on Computing · doi:10.1137/s0097539792236882 · Cited by 185
On the power of randomization in online algorithms
Ben-David, S., Borodin, A., Karp, R., Tardos, G., & Wigderson, A. (1990) · Proceedings of the twenty-second annual ACM symposium on Theory of computing - STOC '90 · doi:10.1145/100216.100268 · Cited by 174
“But as evident in the discussion provided by Karlin, et al [11] the issue transcends particular problems in data structures or paging.”
BackgroundMethodCompetitive routing of virtual circuits in ATM networks
Plotkin, S. (1995) · IEEE Journal on Selected Areas in Communications · doi:10.1109/49.400667 · Cited by 164
“This concept was introduced in [39] and further developed in [ 25 , 15, 33].”
MethodEmpirical studies of competitve spinning for a shared-memory multiprocessor
Karlin, A. R., Li, K., Manasse, M. S., & Owicki, S. (1991) · Proceedings of the thirteenth ACM symposium on Operating systems principles · doi:10.1145/121132.286599 · Cited by 165
Self-citationHow to learn an unknown environment. I: the rectilinear case
Deng, X., Kameda, T., & Papadimitriou, C. (1998) · Journal of the ACM · doi:10.1145/274787.274788 · Cited by 161
An Optimal On-Line Algorithm for K Servers on Trees
Chrobák, M., & Larmore, L. L. (1991) · SIAM Journal on Computing · doi:10.1137/0220008 · Cited by 161
“Quite surprisingly, this algorithm turns out to be equivalent to the Flush-When-Full cache strategy from [6].”
MethodCompetitive randomized algorithms for non-uniform problems
Karlin, A. R., Manasse, M. S., McGeoch, L. A., & Owicki, S. S. (1990) · Symposium on Discrete Algorithms · doi:10.5555/320176.320216 · Cited by 156
Self-citationData replication for mobile computers
Huang, Y., Sistla, P., & Wolfson, O. (1994) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/191839.191845 · Cited by 154
“We [1, 2, 6, 7, 11, 14, 15, 23, 26, 27, 24, 25, 28, 30, 35]).”
Competitive Algorithms for Distributed Data Management
Bartal, Y., Fiat, A., & Rabani, Y. (1995) · Journal of Computer and System Sciences · doi:10.1006/jcss.1995.1073 · Cited by 146
“[KMRS] to get a lower bound of 3 for data migration algorithms.”
BackgroundA new measure for the study of on-line algorithms
Ben-David, S., & Borodin, A. (1994) · Algorithmica · doi:10.1007/bf01294264 · Cited by 141
Memory consistency models for shared-memory multiprocessors
Gharachorloo, K. (1995) · Cited by 146
On-line scheduling in the presence of overload
Baruah, S., Koren, G., Mishra, B., Raghunathan, A. U., Rosier, L. E., & Shasha, D. E. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1991.185354 · Cited by 148
CALMS: Cloud-assisted live media streaming for globalized demands with time/region diversities
Wang, F., Liu, J., & Chen, M. (2012) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infcom.2012.6195578 · Cited by 140
“Such decision problem shares the same “rent-or-buy” structure as the classic ski-rental problem [9].”
BackgroundCompetitive k-server algorithms
Fiat, A., Rabani, Y., & Ravid, Y. (1994) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(05)80060-1 · Cited by 135
A survey of buffer management policies for packet switches
Goldwasser, M. H. (2010) · ACM SIGACT News · doi:10.1145/1753171.1753195 · Cited by 127
Martin, M. M. K., Harper, P. J., Sorin, D. J., Hill, M. D., & Wood, D. A. (2003) · Proceedings - International Symposium on Computer Architecture/Proceedings · doi:10.1145/859618.859642 · Cited by 131
Evaluating The Performance Of Four Snooping Cache Coherency Protocols
Eggers, S. J., & Katz, R. H. (1989) · Proceedings - International Symposium on Computer Architecture/Proceedings · doi:10.1145/74925.74927 · Cited by 131
Dynamic TCP acknowledgement and other stories about e/(e-1)
Karlin, A. R., Mathieu, C., & Randall, D. (2001) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/380752.380845 · Cited by 155
“There is a natural deterministic online algorithm that achieves a competitive ratio of 2 [ 8 ], and a randomized online algorithm that achieves a competitive ratio of e/(e − 1) (which is about 1.58) in the limit as the ratio between the buy cost and the rent cost becomes large [7].”
BackgroundInfluentialSelf-citationCompetitive distributed file allocation
Awerbuch, B., Bartal, Y., & Fiat, A. (1993) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/167088.167142 · Cited by 121
Deng, X., & Papadimitriou, C. H. (1999) · Journal of Graph Theory · doi:10.1002/(sici)1097-0118(199911)32:3 · Cited by 120
Memory versus randomization in on-line algorithms
Rajhavan, P., & Snir, M. (1994) · IBM Journal of Research and Development · doi:10.1147/rd.386.0683 · Cited by 119
Reducing TLB and memory overhead using online superpage promotion
Romer, T. H., Ohlrich, W. H., Karlin, A. R., et al. (1995) · Proceedings - International Symposium on Computer Architecture/Proceedings · doi:10.1145/223982.224419 · Cited by 119
Self-citationD/sup over/; an optimal on-line scheduling algorithm for overloaded real-time systems
Koren, G., & Shasha, D. E. (2003) · IEEE Real-Time Systems Symposium (RTSS) · doi:10.1109/real.1992.242650 · Cited by 120
Deng, X., & Papadimitriou, C. H. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/fscs.1990.89554 · Cited by 116
“Thus, following the approach introduced for a system management problem [19, 15, 11] and robot navigation problem [3, 17], we are interested in obtaining strategies that minimize the performance ratio of the cost of a strategy utilizing available information and the cost of the optimal strategy.”
BackgroundStrongly Competitive Algorithms for Paging with Locality of Reference
Irani, S., Karlin, A. R., & Phillips, S. (1996) · SIAM Journal on Computing · doi:10.1137/s0097539792236353 · Cited by 128
“1This terminology differs slightly from that of [6, 8], where strongly competitive was defined as achieving the competitive ratio ck (G).”
BackgroundSelf-citationImproving Online Algorithms via ML Predictions
Kumar, R., Purohit, M., & Svitkina, Z. (2024) · arXiv · doi:10.48550/arxiv.2407.17712 · Cited by 111
Using Prediction to Accelerate Coherence
Mukherjee, S. S., & Hill, M. D. (1998) · Proceedings - International Symposium on Computer Architecture/Proceedings · doi:10.1145/279358.279386 · Cited by 106
“Other examples of hardware predictors are described in [ 17 , 5, 29, 28].”
Edmonds, J. A. (2000) · Theoretical Computer Science · doi:10.1016/s0304-3975(99)00186-3 · Cited by 108
Online Routing Problems: Value of Advanced Information as Improved Competitive Ratios
Jaillet, P., & Wagner, M. R. (2006) · Transportation Science · doi:10.1287/trsc.1060.0147 · Cited by 102
“Karlin, Manasse, Rudolph, Sleator [14] introduced the notion of a competitive ratio.”
BackgroundOn-line admission control and circuit routing for high performance computing and communication
Awerbuch, B., Gawlick, R., Leighton, T., et al. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365675 · Cited by 100
Channel Assignment and Graph Multicoloring
Narayanan, L. (2002) · doi:10.1002/0471224561.ch4 · Cited by 99
“of online algorithms: that of competitive ratios [ 25 , 3]. Given an online algorithm”
BackgroundCompetitive algorithms for replication and migration problems
Black, D. L., & Sleator, D. D. (2009) · KiltHub Repository · doi:10.1184/r1/6604253 · Cited by 98
Self-citationFleischer, R. (2001) · Theoretical Computer Science · doi:10.1016/s0304-3975(00)00266-8 · Cited by 97
Randomized competitive algorithms for the list update problem
Reingold, N., Westbrook, J., & Sleator, D. D. (1994) · Algorithmica · doi:10.1007/bf01294261 · Cited by 96
Self-citationFleischer, R. (1998) · Lecture notes in computer science · doi:10.1007/3-540-68535-9_10 · Cited by 95
Reactive synchronization algorithms for multiprocessors
Lim, B.-H., & Agarwal, A. K. (1994) · ACM SIGPLAN Notices · doi:10.1145/195470.195490 · Cited by 91
Random walks on weighted graphs and applications to on-line algorithms
Coppersmith, D., Doyle, P. G., Raghavan, P., & Snir, M. (1993) · Journal of the ACM · doi:10.1145/174130.174131 · Cited by 90
“1 Overview Much recent work has dealt with the competitive analysis of on-line algorithms [5, 16, 18].”
BackgroundPreemptive multiprocessor scheduling with rejection
Seiden, S. S. (2001) · Theoretical Computer Science · doi:10.1016/s0304-3975(00)00288-7 · Cited by 90
“The term competitive analysis originated in [12].”
Koutsoupias, E. (2009) · Computer Science Review · doi:10.1016/j.cosrev.2009.04.002 · Cited by 103
“Karlin, Manasse, Rudolph, and Sleator [KMRS86, KMRS88 ] used the framework to study snoopy caching (a caching technique for multiprocessors that share a common bus), introduced the term competitive analysis, and raised the question of applying competitive analysis to other online problems.”
MethodDistributed algorithms for dynamic replication of data
Wolfson, O., & Jajodia, S. (1992) · doi:10.1145/137097.137858 · Cited by 88
Simple and Effective Dynamic Provisioning for Power-Proportional Data Centers
Lu, T., Chen, M., & Andrew, L. L. H. (2012) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2012.241 · Cited by 99
“Second, each individual server is actually solving a classic “ski-rental” (rent-or-buy) problem [26].”
Competitive paging with locality of reference
Borodin, A., Raghavan, P., Irani, S., & Schieber, B. (1991) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/103418.103422 · Cited by 96
“[11].”
BackgroundInfluentialJitter control in QoS networks
Mansour, Y., & Patt-Shamir, B. (2001) · IEEE/ACM Transactions on Networking · doi:10.1109/90.944346 · Cited by 83
The relative worst order ratio for online algorithms
Boyar, J., & Favrholdt, L. M. (2007) · ACM Transactions on Algorithms · doi:10.1145/1240233.1240245 · Cited by 78
“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.”
BackgroundResultInfluentialMaking commitments in the face of uncertainty
Awerbuch, B., Azar, Y., Fiat, A., et al. (1996) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/237814.238000 · Cited by 79
Algorithms for optimizing the bandwidth cost of content delivery
Adler, M., Sitaraman, R. K., & Venkataramani, H. (2011) · Computer Networks · doi:10.1016/j.comnet.2011.07.015 · Cited by 83
“( The algorithm which achieves the bound for the ski rental problem similar to the randomized online algorithm for the snoopy caching problem [10].)”
On-Line Load Balancing of Temporary Tasks
Azar, Y., Kalyanasundaram, B., Plotkin, S. A., et al. (1997) · Journal of Algorithms · doi:10.1006/jagm.1995.0799 · Cited by 76
“Since the arriving tasks have to be assigned without knowledge of the future tasks, it is natural to evaluate the performance in terms of the competitive ratio (this concept was introduced in [17] and further developed in [11, 7, 13]).”
BackgroundLoad Balancing With Multi-Level Signals for Lossless Datacenter Networks
Hu, J., Zeng, C., Wang, Z., et al. (2024) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2024.3366336 · Cited by 75
Hajek, B. (2001) · Cited by 75
A guessing game and randomized online algorithms
Seiden, S. S. (2000) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/335305.335385 · Cited by 91
“The term competitive analysis originated in 18.”
An evaluation of fine-grain producer-initiated communication in cache-coherent multiprocessors
Shafi, H., Hall, J., Adve, S. V., & Adve, V. (2002) · IEEE International Symposium on High-Performance Computer Architecture (HPCA) · doi:10.1109/hpca.1997.569661 · Cited by 74
SIGACT news online algorithms column 8
Chrobák, M. (2005) · ACM SIGACT News · doi:10.1145/1086649.1086670 · Cited by 72
Memory versus randomization in on-line algorithms: Extended abstract
Raghavan, P., & Snir, M. (1989) · Lecture notes in computer science · doi:10.1007/bfb0035792 · Cited by 113
“FWF: (Flush-When-Full, [5]) Whenever a miss occurs an invalid entry is evicted, and the newly loaded entry is marked as valid; if there are no invalid entries then all entries are invalidated.”
BackgroundMethodDynamic TCP Acknowledgment and Other Stories about e/(e - 1)
Karlin, Kenyon, & Randall (2003) · Algorithmica · doi:10.1007/s00453-003-1013-x · Cited by 73
“There is a natural deterministic online algorithm that achieves a competitive ratio of 2 [ 8 ], and a randomized online algorithm that achieves a competitive ratio of e/(e − 1) (which is about 1.58) in the limit as the ratio between the buy cost and the rent cost becomes large [7].”
BackgroundInfluentialMeasuring the problem-relevant information in input
Dobrev, S., Kráľovič, R., & Pardubská, D. (2009) · RAIRO - Theoretical Informatics and Applications · doi:10.1051/ita/2009012 · Cited by 72
Martin, M. M. K., Sorin, D. J., Hill, M. D., & Wood, D. A. (2004) · IEEE International Symposium on High-Performance Computer Architecture (HPCA) · doi:10.1109/hpca.2002.995715 · Cited by 71
“Competitive snoopy caching adapts between an invalidate and an update protocol [16] to limit the overhead to within a factor of two of optimal.”
BackgroundTwo-sided Online Bipartite Matching and Vertex Cover: Beating the Greedy Algorithm
Wang, Y., & Wong, S. C.-W. (2015) · Lecture notes in computer science · doi:10.1007/978-3-662-47672-7_87 · Cited by 71
“The ski rental problem was first studied in [18].”
BackgroundKarlin, A. R., Phillips, S. J., & Raghavan, P. (1992) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1992.267771 · Cited by 69
“The underpinnings of competitive paging were laid in [12].”
BackgroundSelf-citationCompetitive Optimal On-Line Leasing
El‐Yaniv, R., Kaniel, R., & Linial, N. (1999) · Algorithmica · doi:10.1007/pl00009279 · Cited by 68
“[29].”
On-line analysis of the TCP acknowledgment delay problem
Dooly, D. R., Goldman, S. A., & Scott, S. (2001) · Journal of the ACM · doi:10.1145/375827.375843 · Cited by 81
“Related Work We use standard competitive analysis [Sleator and Tarjan 1985; Karlin et al. 1988; Borodin et al. 1992] to evaluate our algorithms.”
MethodDistributed Online Frequency Assignment in Cellular Networks
Janssen, J., Kriz̧anc, D., Narayanan, L., et al. (2000) · Journal of Algorithms · doi:10.1006/jagm.1999.1068 · Cited by 68
“We adapt a standard yardstick for measuring the efficacy of online algorithms: that of competilive ratios [ 6 ].”
MethodApplication transformations for energy and performance-aware device management
Heath, T., Pinheiro, E., Hom, J., et al. (2002) · doi:10.5555/645989.674304 · Cited by 68
On the Influence of Lookahead in Competitive Paging Algorithms
Albers, S. (1997) · Algorithmica · doi:10.1007/pl00009158 · Cited by 68
“We analyze the performance of on-line paging algorithms using competitive analysis [14], [10].”
MethodCompetitive algorithms for distributed data management (extended abstract)
Bartal, Y., Fiat, A., & Rabani, Y. (1992) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/129712.129717 · Cited by 68
“Our algorithms are simple distributed versions of the deterministic Flush-when-fill [KMRS] and the randomized Marking algorithm [FKLMSYl.”
MethodInfluentialCompetitive solutions for online financial problems
El‐Yaniv, R. (1998) · ACM Computing Surveys · doi:10.1145/274440.274442 · Cited by 68
An online optimization approach to post-disaster road restoration
Akbari, V., Shiri, D., & Salman, F. S. (2021) · Transportation Research Part B Methodological · doi:10.1016/j.trb.2021.05.017 · Cited by 66
Ramsey-type theorems for metric spaces with applications to online problems
Bartal, Y., Bollobás, B., & Mendel, M. (2006) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2005.05.008 · Cited by 63
Scheduling parallel machines on-line
Shmoys, D. B., Wein, J. M., & Williamson, D. P. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1991.185361 · Cited by 71
Albers, S., & Leonardi, S. (1999) · ACM Computing Surveys · doi:10.1145/333580.333583 · Cited by 65
“Online problems had been investigated already in the seventies and early eighties but an extensive, systematic study started only when Sleator and Tarjan [41] suggested comparing an online algorithm to an optimal oine algorithm and Karlin, Manasse, Rudolph and Sleator [ 29 ] coined the term competitive analysis.”
A decision support system for optimizing dynamic courier routing operations
Lin, C., Choy, K. L., Ho, G. T. S., et al. (2014) · Expert Systems with Applications · doi:10.1016/j.eswa.2014.04.036 · Cited by 65
The Accommodating Function: A Generalization of the Competitive Ratio
Boyar, J., Larsen, K. S., & Nielsen, M. N. (2001) · SIAM Journal on Computing · doi:10.1137/s0097539799361786 · Cited by 65
Online Scheduling with Hard Deadlines
Goldman, S. A., Parwatikar, J., & Suri, S. (2000) · Journal of Algorithms · doi:10.1006/jagm.1999.1060 · Cited by 65
“We use standard competitive analysis [13, 11, 6] to evaluate our algorithms.”
MethodMOCA: a multiprocessor on-line competitive algorithm for real-time system scheduling
Koren, G., & Shasha, D. E. (1994) · Theoretical Computer Science · doi:10.1016/0304-3975(94)90165-1 · Cited by 64
Peak-Aware Online Economic Dispatching for Microgrids
Zhang, Y., Hajiesmaili, M., Cai, S., Chen, M., & Zhu, Q. (2016) · IEEE Transactions on Smart Grid · doi:10.1109/tsg.2016.2551282 · Cited by 77
Boyar, J., & Larsen, K. S. (1999) · Algorithmica · doi:10.1007/pl00009286 · Cited by 61
“Karlin et al. [ 13 ] defined an algorithm to be c-competitive if its cost on any sequence is within a factor of c of the cost of the optimal off-line algorithm, plus a constant, on that sequence.”
BackgroundOnline stochastic optimization under time constraints
Hentenryck, P. V., Bent, R. W., & Upfal, E. (2009) · Annals of Operations Research · doi:10.1007/s10479-009-0605-5 · Cited by 70
“Their quality is measured by a competitive analysis [24] that compares the online solution with the result of an “offline” algorithm that “knows” the whole sequence of requests in advance.”
MethodMigration Towards Cloud-Assisted Live Media Streaming
Wang, F., Liu, J., Chen, M., et al. (2014) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2014.2362541 · Cited by 61
“This suggests that one may map the demand forecast problem to the classic ski-rental problem [9] and apply the simple break-even online algorithm.”
MethodRouting and admission control in general topology networks with Poisson arrivals
Kamath, A. P., Palmon, O., & Plotkin, S. A. (1996) · doi:10.5555/313852.314073 · Cited by 61
Online Vehicle Routing Problems: A Survey
Jaillet, P., & Wagner, M. R. (2008) · Operations research, computer science. Interface series · doi:10.1007/978-0-387-77778-8_10 · Cited by 60
“Karlin, Manasse, Rudolph, Sleator [29] introduced the notion of a competitive ratio.”
BackgroundRegrets only! online stochastic optimization under time constraints
Bent, R. W., & Hentenryck, P. V. (2004) · Cited by 60
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.