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 401–500 of 619
Online Paging with Heterogeneous Cache Slots
Chrobák, M., Haney, S., Liaee, M., Panigrahi, D., Rajaraman, R., Sundaram, R., & Young, N. E. (2024) · Algorithmica · doi:10.1007/s00453-024-01270-z · Cited by 3
“Together Theorems 5 and 1 (ii) imply that, as a function of |S| and k , the optimal deterministic ratio for Slot-Heterogenous Paging is polynomial.”
Advanced Techniques for Dynamic Programming
Bein, W. W. (2013) · Springer eBooks · doi:10.1007/978-1-4419-7997-1_28 · Cited by 5
On Approximation Algorithms for Data Mining Applications
Afrati, F. (2006) · Lecture notes in computer science · doi:10.1007/11671541_1 · Cited by 4
“analysis [69], or I/O efficient algorithms [98].”
Scheduling Two Machines with Release Times
Noga, J., & Seiden, S. S. (1999) · Lecture notes in computer science · doi:10.1007/3-540-48777-8_29 · Cited by 4
“The term competitive analysis originated in [ 12 ].”
BackgroundOn-Line Edge-Coloring with a Fixed Number of Colors
Favrholdt, L. M., & Nielsen, M. N. (2000) · Lecture notes in computer science · doi:10.1007/3-540-44450-5_8 · Cited by 4
Uniform multipaging reduces to paging
Liberatore, V. (1998) · Information Processing Letters · doi:10.1016/s0020-0190(98)00080-5 · Cited by 3
“An on-line strategy is said to be strongly competitive if it achieves the best possible competitive ratio [5, 6].”
BackgroundComparing First-Fit and Next-Fit for online edge coloring
Ehmsen, M. R., Favrholdt, L. M., Kohrt, J. S., et al. (2010) · Theoretical Computer Science · doi:10.1016/j.tcs.2010.01.015 · Cited by 4
“Roughly speaking, the competitive ratio of an online algorithmA is theworst-case ratio of the performance of A to the performance of an optimal offline algorithm over all possible request sequences [2,3].”
BackgroundGeneralized Reordering Buffer Management
Azar, Y., Englert, M., Gamzu, I., & Kidron, E. (2014) · Warwick Research Archive Portal (University of Warwick) · doi:10.4230/lipics.stacs.2014.87 · Cited by 4
Analysis of buffer replacement policies for WWW proxy
Kim, I. H., Yeom, H. Y., & Lee, J. (1998) · ACM Symposium on Applied Computing · doi:10.1145/330560.330654 · Cited by 4
Randomized k-server algorithms for growth-rate bounded graphs
Bartal, Y., & Mendel, M. (2004) · doi:10.5555/982792.982895 · Cited by 4
Page Migration in Dynamic Networks
Bieńkowski, M., & der Heide, F. M. A. (2005) · Lecture notes in computer science · doi:10.1007/11549345_1 · Cited by 4
List Factoring and Relative Worst Order AnalysisPreprint
Ehmsen, M. R., Kohrt, J. S., & Larsen, K. S. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1009.5787 · Cited by 4
“The most standard performance measure for online algorithms is competitive analysis [20, 22, 28].”
BackgroundManasse, M. S. (2008) · Springer eBooks · doi:10.1007/978-0-387-30162-4_378 · Cited by 5
Self-citationКриворізький державний педагогічний університет, К., & Державний університет, ". П. (2021) · doi:10.31812/123456789/4366 · Cited by 4
Single machine lot scheduling to minimize maximum weighted completion time
Zheng, F., Li, N., Liu, M., et al. (2025) · Journal of Combinatorial Optimization · doi:10.1007/s10878-025-01327-x · Cited by 3
Zheng, F., Chen, Y., Liu, M., et al. (2022) · Journal of Combinatorial Optimization · doi:10.1007/s10878-022-00882-x · Cited by 3
“Karlin et al. (1988) proved a best competitive ratio of 2 − 1 / k for the ski-rental problem.”
BackgroundSki Rental Problem with Dynamic Pricing
Bieńkowski, M. (2008) · Cited by 3
Runtime optimization of join location in parallel data management systems
Chandra, B., & Sudarshan, S. (2017) · Proceedings of the VLDB Endowment · doi:10.14778/3137628.3137656 · Cited by 3
“The classical ski-rental problem [13] refers to the online problem in which there is a choice between paying a renting cost for each usage of the object versus paying once for the purchase of the object after which no cost for renting needs to be paid.”
Epstein, L., Imreh, C., Levin, A., & Nagy-György, J. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-22006-7_17 · Cited by 3
“Using methods related to the Ski-Rental problem [ 21 ], we develop a general reduction of the problem with rejection to the problem with bypassing, showing that an αk-competitive algorithm for the case of bypassing can be converted (using this algorithm as a black box) into a (4αk + 1)-competitive algorithm for the pr…”
MethodDispatching Equal-Length Jobs to Parallel Machines to Maximize Throughput
Bunde, D. P., & Goldwasser, M. H. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-13731-0_33 · Cited by 3
Aprea, M., Feuerstein, E., Sadovoy, G., et al. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-02158-9_5 · Cited by 3
“Competitive analysis [13, 14] is a type of worst case analysis where the performance of an algorithm for a problem is compared to that of an optimal offline algorithm.”
MethodScheduling Jobs on Grid Processors
Boyar, J., & Favrholdt, L. M. (2006) · Lecture notes in computer science · doi:10.1007/11785293_5 · Cited by 3
An online scheduler for hardware accelerators on general-purpose operating systems
Sheldon, D., & Forin, A. (2010) · Cited by 3
Online Algorithms for Automotive Idling Reduction With Effective Statistics
Dong, C., Zeng, H., & Chen, M. (2015) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/tcad.2015.2469779 · Cited by 3
“The existing solutions to be compared with include TOI, NEV, DET [9], N-Rand [17], and MOM-Rand [10].”
BackgroundMethodInfluentialCompetitive Analysis of Two Special Online Device Replacement Problems
Xin, C., Ma, W., & Yang, L. (2008) · Journal of Computer Science and Technology · doi:10.1007/s11390-008-9122-2 · Cited by 4
“Online problems had already been investigated in the 1970s and early 1980s but an extensive and systematic study started only when Sleator and Tarjan([15]) suggested comparing an online algorithm to an optimal offline algorithm and Karlin et al.([16]) coined the term competitive analysis.”
Engelberg, R., & Naor, J. S. (2007) · Symposium on Discrete Algorithms · doi:10.5555/1283383.1283400 · Cited by 3
On-Line Taxi Problem on the Benefit-Cost Graphs
Ma, W., & Wang, K. (2006) · International Conference on Machine Learning and Cybernetics · doi:10.1109/icmlc.2006.258494 · Cited by 3
“On-line problems had been systematically investigated only when Sleator and Tarjian [13] suggested comparing an on-line algorithm to an optimal off-line algorithm and Karlin, Manasse, Rudolph and Sleator [ 14 ] coined the term competitive analysis.”
MethodThe Semi-stochastic Ski-rental Problem
Mądry, A., & Panigrahi, D. (2011) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.fsttcs.2011.300 · Cited by 6
Energy Efficiency and Renewable Energy Management with Multi-State Power-Down Systems
Andro-Vasko, J., Bein, W. W., & Ito, H. (2019) · Information · doi:10.3390/info10020044 · Cited by 3
“Under competitive analysis, for the two-state problem, an optimal online algorithm, here referred to as S , is well known for this problem [13]: S switches to ON at a service request.”
BackgroundResultInfluentialde Lima, M. S., Felice, M. C. S., & Lee, O. (2019) · Discrete Applied Mathematics · doi:10.1016/j.dam.2019.05.013 · Cited by 3
“This problem reduces to PP if rt ≤ 1 for every day t, to MPP if M =∞, and to the ski rental problem [26] if K = 1 and δ1 =∞.”
BackgroundOnline Multi-Coloring with Advice
Christ, M. G., Favrholdt, L. M., & Larsen, K. S. (2015) · Lecture notes in computer science · doi:10.1007/978-3-319-18263-6_8 · Cited by 3
Relative Worst-order Analysis: A Survey
Boyar, J., Favrholdt, L. M., & Larsen, K. S. (2021) · ACM Computing Surveys · doi:10.1145/3425910 · Cited by 5
Patt-Shamir, B., & Yadai, E. (2020) · ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) · doi:10.1145/3350755.3400280 · Cited by 6
Joint replenishment meets scheduling
Györgyi, P., Kis, T., Tamási, T., & Békési, J. (2022) · Journal of Scheduling · doi:10.1007/s10951-022-00768-0 · Cited by 5
“58, and both bounds are tight [23], [22].”
BackgroundOnline search for a hyperplane in high-dimensional Euclidean space
Antoniadis, A., Hoeksma, R., Kisfaludi-Bak, ., et al. (2022) · Information Processing Letters · doi:10.1016/j.ipl.2022.106262 · Cited by 3
A cost efficient online algorithm for automotive idling reduction
Dong, C., Zeng, H., & Chen, M. (2014) · doi:10.1109/dac.2014.6881419 · Cited by 3
On-line algorithms for cache sharing
Bern, M. W., Greene, D., & Raghunathan, A. U. (1993) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/167088.167205 · Cited by 3
The dynamic predicate stashing copy problem
Sansò, B., & Soumis, F. (1993) · Networks · doi:10.1002/net.3230230806 · Cited by 3
Performance effects of program structures on a snoop-cached multiprocessor system
Yamanouchi, N. (1992) · Future Generation Computer Systems · doi:10.1016/0167-739x(92)90011-y · Cited by 3
Online algorithms for finger searching
Cole, R. J., & Raghunathan, A. U. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/fscs.1990.89569 · Cited by 3
Feuerstein, E. (1997) · Theoretical Computer Science · doi:10.1016/s0304-3975(97)89513-8 · Cited by 3
“Another k-competitive Mgorithm for paging called Flush-When-Full (FWF) has been presented in [ 10 ].”
Integration and evaluation of cache coherence protocols for multiprocessor socs
Suh, T. (2006) · UPT. Syiah Kuala University Library (Syiah Kuala University) · Cited by 3
Flow Equilibria via Online Surge PricingPreprint
Fiat, A., Mansour, Y., & Shultz, L. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1804.09672 · Cited by 7
“e the sum of passenger valuations, but ignore travel costs. In contrast, we ignore the time dimension and focus on the passenger valuations and travel costs. Competitive analysis of online algorithms [23, 22, 15] considers a worst case sequence of online events with respect to the ratio between the performance of an o…”
BackgroundLi, N., Zheng, F., & Liu, M. (2025) · Expert Systems with Applications · doi:10.1016/j.eswa.2025.130959 · Cited by 2
Prediction-Specific Design of Learning-Augmented Algorithms
李, 思., Christianson, N., & Li, T. (2026) · Proceedings of the ACM on Measurement and Analysis of Computing Systems · doi:10.1145/3788100 · Cited by 2
Seat Reservation Allowing Seat Changes
Boyar, J., Krarup, S., & Nielsen, M. N. (2001) · Electronic Notes in Theoretical Computer Science · doi:10.1016/s1571-0661(04)00163-x · Cited by 2
“We use competitive analysis; the standard competitive ratio [9, 11 , 13, 14], the competitive ratio on accommodating sequences [6] 1, and the accommodating function [5, 7]. Two dieren t pricing policies are”
MethodExact distributional analysis of online algorithms with lookahead
Dunke, F., & Nickel, S. (2020) · 4OR · doi:10.1007/s10288-020-00442-1 · Cited by 2
Online Paging for Flash Memory Devices
Kovács, A., Meyer, U., Moruz, G., & Negoescu, A. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-10631-6_37 · Cited by 1
“The resulting measure, denoted later competitive ratio [13], states that an online algorithm A is c-competitive if A(σ) ≤ c · OPT (σ) + b for any input sequence σ, where b is a constant, and A(σ) and OPT (σ) are the costs of A and an optimal offline algorithm respectively (if A is randomized, A(σ) is the expected cost…”
BackgroundOn Multiprocessor System Scheduling
Deng, X., & Dymond, P. W. (1998) · Journal of Combinatorial Optimization · doi:10.1023/a:1009790611712 · Cited by 2
Online Dual Edge Coloring of Paths and Trees
Favrholdt, L. M., & Mikkelsen, J. W. (2015) · Lecture notes in computer science · doi:10.1007/978-3-319-18263-6_16 · Cited by 2
On the bicriteria k -server problem
Flammini, M., & Nicosia, G. (2010) · ACM Transactions on Algorithms · doi:10.1145/1868237.1868244 · Cited by 2
“De.nition 2.1 ([Karlin et al. 1988; Sleator and Tarjan 1985]).”
BackgroundInfluentialA Flexible Java Representation for Uncertainty in Online Operations-Research Models
Shapiro, J. A., Powell, W. B., & Bernstein, D. H. (2001) · INFORMS journal on computing · doi:10.1287/ijoc.13.1.29.9749 · Cited by 2
Admission control and routing in multi-hop wireless networks
Jaramillo, J. J., & Srikant, R. (2008) · Proceedings of the IEEE Conference on Decision & Control, including the Symposium on Adaptive Processes · doi:10.1109/cdc.2008.4738981 · Cited by 2
“The concept of competitive ratio was first introduced by [7] and further developed by [8]–[10].”
BackgroundOnline Traveling Salesman Problems with Flexibility
Jaillet, P., & Lu, X. (2009) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/dagsemproc.09261.19 · Cited by 2
SIGACT news online algorithms column 14
Chrobák, M. (2009) · ACM SIGACT News · doi:10.1145/1620491.1620508 · Cited by 2
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 Performance Evaluation Review · doi:10.1145/3376930.3376953 · Cited by 3
Distributed Mega-Datasets: The Need for Novel Computing Primitives
Semmler, N., Smaragdakis, G., & Feldmann, A. (2019) · IEEE International Conference on Distributed Computing Systems (ICDCS) · doi:10.1109/icdcs.2019.00167 · Cited by 2
“To this end, we rely on results derived for the classical ski rental problem [8], [12].”
BackgroundMethodFuzzy Model for Determining the Risk Premium to the Rental Rate When Renting Technological Equipment
Ekhlakov, Y. P., Saprunov, S. O., Васильевич, С. П., & Sidorov, A. (2023) · Mathematics · doi:10.3390/math11030541 · Cited by 2
“In general view, this task inverts the famous “ski-renting” task [20].”
BackgroundResultOnline Minimum Spanning Trees with Weight Predictions
Berg, M., Boyar, J., Favrholdt, L. M., et al. (2023) · Lecture notes in computer science · doi:10.1007/978-3-031-38906-1_10 · Cited by 2
Competitive analysis for the on-line Vehicle Routing Problem
Ma, W., Dandan, D., & Wang, K. (2010) · International Conference on New Trends in Information Science and Service Science · Cited by 2
Edge replication strategies for wide-area distributed processing
Semmler, N., Rost, M., Smaragdakis, G., & Feldmann, A. (2020) · doi:10.1145/3378679.3394532 · Cited by 2
“Clearly, this strategy is also 2-competitive and the result by Karlin et al. [9] also implies that no c -competitive strategy can exist for c < 2.”
MethodOnline Failure Diagnosis in Interdependent Networks
Shiri, D., & Akbari, V. (2021) · Operations Research Forum · doi:10.1007/s43069-021-00055-2 · Cited by 2
Decrease and reset for power-down
Andro-Vasko, J., Bein, W. W., Ito, H., Kasahara, S., & Kawahara, J. I. (2021) · Energy Systems · doi:10.1007/s12667-021-00475-3 · Cited by 2
“This situation is analogous to the noted ski rental problem [25].”
BackgroundResultThe list update problem and the retrieval of sets
d’Amore, F., & Liberatore, V. (1992) · Lecture notes in computer science · doi:10.1007/3-540-55706-7_16 · Cited by 2
Cache Coherence in Multiprocessors: A Survey
Yousif, M. S., Thazhuthaveetil, M. J., & Das, C. R. (1995) · Advances in computers · doi:10.1016/s0065-2458(08)60546-x · Cited by 2
More on Weighted Servers or Fifo is Better than Lru
Epstein, L., Imreh, C., & van Stee, R. (2002) · Lecture notes in computer science · doi:10.1007/3-540-45687-2_21 · Cited by 2
Online optimization in routing and scheduling
Wagner, M. R. (2006) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 2
The Impact of Cache Coherence Protocols on Parallel Logic Programming Systems
Dutra, I., Costa, V. S., & Bianchini, R. (2000) · Lecture notes in computer science · doi:10.1007/3-540-44957-4_86 · Cited by 2
On-Line Resource Management with Application to Routing and Scheduling
Leonardi, S., & Marchetti-Spaccamela, A. (1999) · Algorithmica · doi:10.1007/pl00009270 · Cited by 2
“We usecompetitive analysis[15], [16], [20], [19], [24], [30] for the analysis of on-line algorithms; competitive analysis compares an on-line”
MethodThe working set algorithm has competitive ratio less than two
Park, K., Min, S. L., & Cho, Y. (1997) · Information Processing Letters · doi:10.1016/s0020-0190(97)00128-2 · Cited by 2
Competitive Analysis for the On-line Truck Transportation Problem
Ma, W., Liu, J. N. K., Chen, G., et al. (2006) · Journal of Global Optimization · doi:10.1007/s10898-005-2849-1 · Cited by 2
“The systematic study of on-line problems started when Sleator and Tarjan [8] suggested comparing an on-line algorithm with an optimal off-line algorithm and Karlin, Manasse, Rudolph and Sleator [9] coined the term competitive analysis.”
MethodTight competitive ratios for parallel disk prefetching and caching
Hon, W.-K., Shah, R., Varman, P., & Vitter, J. S. (2008) · ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) · doi:10.1145/1378533.1378593 · Cited by 2
“Some fundamental results were given by [1, 4, 7, 27].”
Disruption Management of Rolling Stock in Passenger Railway TransportationPreprint
Nielsen, L. K., & Maróti, G. (2009) · RePEc: Research Papers in Economics · Cited by 2
Fine-grain distributed shared memory on clusters of workstations
Schoinas, I., & Hill, M. D. (1998) · Cited by 2
Reducing coherence-related overhead in multiprocessor systems
Prete, C. A., Ricciardi, L. M., & Prina, G. (2002) · Proceedings - Euromicro Workshop on Parallel and Distributed Processing/Proceedings · doi:10.1109/empdp.1995.389177 · Cited by 2
Comparing First-Fit and Next-Fit for Online Edge Coloring
Ehmsen, M. R., Favrholdt, L. M., Kohrt, J. S., et al. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-92182-0_11 · Cited by 2
Data caching for telephony services
Carpenter, T. J., Carter, R., Cochinwala, M., & Eiger, M. I. (2002) · International Database Engineering and Applications Symposium (IDEAS) · doi:10.1109/ideas.2000.880568 · Cited by 2
“If all items are marked, unmark them, evict an arbitrary item, and continue marking cached items as they arc subsequently inserted into or accessed from the cache [ 5 ].”
BackgroundPaging with connections: FIFO strikes again
Epstein, L., Kleiman, Y., Sgall, J., & van Stee, R. (2007) · Theoretical Computer Science · doi:10.1016/j.tcs.2007.02.009 · Cited by 2
“Although lru outperforms fifo in practice, lru and fifo are known to have the same competitive ratio of k. Further this ratio is known to be the best possible, see [12, 10 ].”
BackgroundCobra: A Framework for Cost Based Rewriting of Database ApplicationsPreprint
Emani, K. V., & Sudarshan, S. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1801.04891 · Cited by 2
“y prefetching asynchronously, and dynamically deciding to prefetch only after a certain number of accesses to minimize the overhead of prefetching. This is similar to the classical ski-rental problem [19] and has been applied earlier in the context of join optimizations in parallel data management systems [20]. Extend…”
MethodRuntime Optimization of Join Location in Parallel Data Management SystemsPreprint
Chandra, B., & Sudarshan, S. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1703.01148 · Cited by 2
“The classical ski-rental problem [13] refers to the online problem in which there is a choice between paying a renting cost for each usage of the object versus paying once for the purchase of the object after which no cost for renting needs to be paid.”
Scheduling Light-trails in WDM RingsPreprint
Pal, S., & Ranade, A. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1112.6254 · Cited by 2
A Comparison of Performance Measures for Online AlgorithmsPreprint
Boyar, J., Irani, S., & Larsen, K. S. (2008) · arXiv (Cornell University) · doi:10.48550/arxiv.0806.0983 · Cited by 2
“It has also been observed that Competitive Analysis sometimes fails to distinguish between algorithms which have very different performance in practice and intuitively differ in quality.”
BackgroundInfluentialCaching with rental cost and zapping
Khare, M., & Young, N. E. (2012) · arXiv · doi:10.48550/arxiv.1208.2724 · Cited by 1
“ngRentMeta is also deterministic, otherwise it is randomized. Corollary1. Theorem 2.5 gives us the following algorithms for rental caching. Deterministic: Using the 2-competitive ski-rental algorithm [12] and kcompetitive algorithm for caching [17], we get a (k + 2)-competitive algorithm for rental caching. Randomized…”
InfluentialCost-Driven Data Replication with Predictions
Zuo, T., Tang, X., & Lee, B. (2024) · ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) · doi:10.1145/3626183.3659964 · Cited by 2
“Such a trade-off appears to resemble that between rent and buy in the classical ski-rental problem [6].”
BackgroundOn Competitiveness of Dynamic Replication for Distributed Data Access
Zuo, T., Tang, X., Lee, B. S., & Cai, J. (2025) · International Conference on Distributed Computing and Networking (ICDCN) · doi:10.1145/3772290.3772303 · Cited by 1
On competitiveness of dynamic replication for distributed data access
Zuo, T., Tang, X., Lee, B. S., & Cai, J. (2026) · Theoretical Computer Science · doi:10.1016/j.tcs.2026.115992 · Cited by 1
Asymptotically Optimal Online Page Migration on Three Points
Matsubayashi, A. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-38016-7_10 · Cited by 1
Improved Space Bounds for Strongly Competitive Randomized Paging Algorithms
Moruz, G., & Negoescu, A. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-39206-1_64
“Online algorithms in general and paging algorithms in particular are typically analyzed in the framework of competitive analysis[11, 15].”
BackgroundThe Frequent Items Problem in Online Streaming under Various Performance Measures
Boyar, J., Larsen, K. S., & Maiti, A. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-40164-0_9 · Cited by 1
On the On-Line k-Taxi Problem with Limited Look Ahead
Ma, W., Gao, T., & Wang, K. (2007) · Lecture notes in computer science · doi:10.1007/978-3-540-73556-4_10 · Cited by 1
Engineering Efficient Paging Algorithms
Moruz, G., Negoescu, A., Neumann, C., & Weichert, V. (2015) · ACM Journal of Experimental Algorithmics · doi:10.1145/2670127 · Cited by 2
Bandwidth Adaptive Cache Coherence Optimizations for Chip Multiprocessors
Kayi, A., Serres, O., & El‐Ghazawi, T. (2013) · International Journal of Parallel Programming · doi:10.1007/s10766-013-0247-8 · Cited by 1
Calculating lower bounds for caching problems
Epstein, L., & van Stee, R. (2007) · Computing · doi:10.1007/s00607-007-0230-6 · Cited by 1
“Further this ratio is known to be the best possible, see [12], [15].”
BackgroundResultEpstein, L., van Stee, R., & Tamir, T. (2007) · Theory of Computing Systems · doi:10.1007/s00224-007-9029-2 · Cited by 1
“Further this ratio is known to be the best possible, see [10, 14].”
BackgroundCompetitive Analysis of Online Price Discount Replacement Problem
Ding, L., Liu, X., & Kang, W. (2009) · International Joint Conference on Computational Sciences and Optimization (CSO) · doi:10.1109/cso.2009.491 · Cited by 1
“[6] introduced the notion of a competitive ratio.”
BackgroundStochastic dominance analysis of online bin coloring algorithms
Hiller, B., & Vredeveld, T. (2009) · Cited by 1
Online Bin Covering: Expectations vs. Guarantees
Christ, M. G., Favrholdt, L. M., & Larsen, K. S. (2013) · Lecture notes in computer science · doi:10.1007/978-3-319-03780-6_20
Machine learning advised algorithms for the ski rental problem with a discount
Bhattacharya, A., & Das, R. (2022) · Theoretical Computer Science · doi:10.1016/j.tcs.2022.10.006 · Cited by 2
Weighted Refinement Types for Counterpoint Composition
Cong, Y. (2023) · doi:10.1145/3609023.3609804 · Cited by 1
Learning-Augmented Online Algorithm for Two-Level Ski-Rental Problem
Zhang, K., Liu, Z., Choi, N., & Ji, B. (2024) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v38i18.30010 · Cited by 6
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.