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 201–300 of 619
The maximum resource bin packing problem
Boyar, J., Epstein, L., Favrholdt, L. M., et al. (2006) · Theoretical Computer Science · doi:10.1016/j.tcs.2006.06.001 · Cited by 21
“Similar to the approximation ratio for approximation algorithms, the performance of deterministic on-line algorithms is measured in comparison with the optimal off-line algorithm OPT [11,17,18].”
MethodEvaluating the performance of four snooping cache coherency protocols
Eggers, S. J., & Katz, R. H. (1989) · ACM SIGARCH Computer Architecture News · doi:10.1145/74926.74927 · Cited by 21
The relative worst order ratio applied to paging
Boyar, J., Favrholdt, L. M., & Larsen, K. S. (2005) · doi:10.5555/1070432.1070534 · Cited by 20
Online ordering policies for a two-product, multi-period stationary newsvendor problem
Zhang, Y., & Yang, X. (2016) · Computers & Operations Research · doi:10.1016/j.cor.2016.04.031 · Cited by 20
Multi-Priority Online Scheduling with Cancellations
Wang, X., & Truong, V. (2017) · Operations Research · doi:10.1287/opre.2017.1653 · Cited by 20
Khanna, S., & Liberatore, V. (2000) · SIAM Journal on Computing · doi:10.1137/s0097539798341399 · Cited by 20
Edmonds, J. A., Chinn, D. D., Brecht, T. B., & Deng, X. (1997) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/258533.258565 · Cited by 22
“This measure was rst introduced in the study of a system memory management problem [6, 11, 17].”
MethodProbability-free solutions to the non-stationary newsvendor problem
Zhang, Y., Vovk, V., & Zhang, W.-G. (2014) · Annals of Operations Research · doi:10.1007/s10479-014-1620-8 · Cited by 23
“It is based on the idea of comparing online and offline performances (Sleator and Tarjan 1985) and uses the competitive ratio to evaluate the online performance (Karlin et al. 1988; Borodin and El-Yaniv 1998).”
BackgroundKayi, A., Serres, O., & El-Ghazawi, T. A. (2014) · IEEE Transactions on Computers · doi:10.1109/tc.2013.217 · Cited by 19
“Write-invalidate versus write-update protocol design has been investigated in many earlier studies [10], [14], [16], [18]–[23].”
ResultOptimal randomized algorithm for a generalized ski-rental with interest rate
Yang, X., Zhang, W., Zhang, Y., & Xu, W. (2012) · Information Processing Letters · doi:10.1016/j.ipl.2012.04.006 · Cited by 19
A Tight Lower Bound for Online Convex Optimization with Switching Costs
Antoniadis, A., & Schewior, K. (2018) · Lecture notes in computer science · doi:10.1007/978-3-319-89441-6_13 · Cited by 21
Competitive distributed file allocation
Awerbuch, B., Bartal, Y., & Fiat, A. (2003) · Information and Computation · doi:10.1016/s0890-5401(03)00055-5 · Cited by 19
Online Randomized Multiprocessor Scheduling
Seiden, S. S. (2000) · Algorithmica · doi:10.1007/s004530010014 · Cited by 20
“Some examples include: deciding which variables to keep in the cache during the execution of a program so as to maximize cache utilization [28], [7], [14], [22], [18], deciding how to distribute data on a network so as to minimize network traffic [ 21 ], [29], [2], [12] and deciding how to schedule a job on some set o…”
BackgroundCompetitive distributed decision-making
Deng, X., & Papadimitriou, C. H. (1996) · Algorithmica · doi:10.1007/bf01940643 · Cited by 19
Scheduling real-time disk transfers for continuous media applications
Long, D. D. E., & Thakur, M. N. (2002) · doi:10.1109/mass.1993.289755 · Cited by 19
Data replication for mobile computers
Huang, Y., Sistla, P., & Wolfson, O. (1994) · ACM SIGMOD Record · doi:10.1145/191843.191845 · Cited by 19
Peak-Aware Online Economic Dispatching for Microgrids
Zhang, Y., Hajiesmaili, M., & Chen, M. (2015) · ACM International Conference on Future Energy Systems (e-Energy) · doi:10.1145/2768510.2768538 · Cited by 21
“Similar to the ski rental problem [12], the break-even point turns out to be the best balance between being aggressive and conservative.”
BackgroundA Comparison of Performance Measures for Online Algorithms
Boyar, J., Irani, S., & Larsen, K. S. (2014) · Algorithmica · doi:10.1007/s00453-014-9884-6 · Cited by 18
“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.”
BackgroundInfluentialApplying “Peeling Onion” approach for competitive analysis in online scheduling with rejection
Ma, R., & Guo, S. (2020) · European Journal of Operational Research · doi:10.1016/j.ejor.2020.08.009 · Cited by 18
On the best possible competitive ratio for the multislope ski-rental problem
Fujiwara, H., Kitano, T., & Fujito, T. (2014) · Journal of Combinatorial Optimization · doi:10.1007/s10878-014-9762-9 · Cited by 18
The influence of lookahead in competitive paging algorithms
Albers, S. (1993) · Lecture notes in computer science · doi:10.1007/3-540-57273-2_39 · Cited by 18
Better bounds on online unit clustering
Ehmsen, M. R., & Larsen, K. S. (2013) · Theoretical Computer Science · doi:10.1016/j.tcs.2013.07.008 · Cited by 17
“To measure the quality of an online algorithm for this problem, we follow previous work on the same topic and use competitive analysis [6,8,7].”
MethodInfluentialMendel, M., & Seiden, S. S. (2004) · Theoretical Computer Science · doi:10.1016/j.tcs.2004.05.015 · Cited by 17
“Formally, given an item request sequence σ, the cost of an online algorithm A on σ, denoted by costA(σ), is the number of faults incurred by A.”
BackgroundRent or Buy Problems with a Fixed Time Horizon
Epstein, L., & Zebedat-Haider, H. (2014) · Theory of Computing Systems · doi:10.1007/s00224-014-9552-x · Cited by 18
“The classic (deterministic) ski rental problem [14–17, 21] is the case where all rental costs are equal, and the number of days is not known in advance (an upper bound on the number of days is not known either).”
A New Approach to Online Scheduling: Approximating the Optimal Competitive Ratio
Günther, E., Maurer, O., Megow, N., et al. (2013) · Max Planck Digital Library · Cited by 17
A theoretical comparison of LRU and LRU-K
Boyar, J., Ehmsen, M. R., Kohrt, J. S., & Larsen, K. S. (2010) · Acta Informatica · doi:10.1007/s00236-010-0123-6 · Cited by 19
“where OPT denotes an optimal off-line algorithm [15,20].”
BackgroundLatency effects of system level power management algorithms
Ramanathan, D., Irani, S., & Gupta, R. K. (2002) · International Conference on Computer Aided Design · doi:10.1109/iccad.2000.896497 · Cited by 17
“The authors in [12] have adapted the results from [5, 4] to the power management problem.”
BackgroundMethodInfluentialWestermann, M. (1999) · Informatik aktuell · doi:10.1007/978-3-662-01069-3_42 · Cited by 17
On the On-line Number of Snacks Problem
Ma, W., You, J., Xu, Y., et al. (2002) · Journal of Global Optimization · doi:10.1023/a:1021253103047 · Cited by 17
Randomized on-line algorithms for the page replication problem
Koga, H. (1993) · Lecture notes in computer science · doi:10.1007/3-540-57568-5_275 · Cited by 17
Access Graphs Results for LRU versus FIFO under Relative Worst Order Analysis
Boyar, J., Gupta, S., & Larsen, K. S. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-31155-0_29 · Cited by 16
“The most standard measure of quality of an online algorithm is competitive analysis [17, 22, 20].”
BackgroundCompetitive strategy for on-line leasing of depreciable equipment
Zhang, Y., Zhang, W.-G., Xu, W., & Li, H. (2011) · Mathematical and Computer Modelling · doi:10.1016/j.mcm.2011.02.036 · Cited by 16
SIGACT news online algorithms column 4
Chrobák, M. (2004) · ACM SIGACT News · doi:10.1145/1027914.1027930 · Cited by 16
On Energy Conservation in Data Centers
Albers, S. (2017) · ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) · doi:10.1145/3087556.3087560 · Cited by 20
“problem, a famous rent-or-buy problem [15, 16, 19, 21].”
Online scheduling problems with flexible release dates: Applications to infrastructure restoration
Nurre, S. G., & Sharkey, T. C. (2017) · Computers & Operations Research · doi:10.1016/j.cor.2017.11.014 · Cited by 16
Feuerstein, & de Loma, S. (2002) · Algorithmica · doi:10.1007/s00453-001-0073-z · Cited by 16
“All the algorithms presented in this paper for the different versions of MTP are based on Flush-When-Full (FWF), a very well knownk-competitive on-line algorithm for Paging, that was introduced in [11].”
MethodPage migration algorithms using work functions
Chrobák, M., Larmore, L. L., Reingold, N., & Westbrook, J. (1993) · Lecture notes in computer science · doi:10.1007/3-540-57568-5_272 · Cited by 16
An improved lower bound for load balancing of tasks with unknown duration
Ma, Y., & Plotkin, S. A. (1997) · Information Processing Letters · doi:10.1016/s0020-0190(97)00085-9 · Cited by 16
Bartal, Y. (1998) · Lecture notes in computer science · doi:10.1007/bfb0029566 · Cited by 15
Using prediction to accelerate coherence protocols
Mukherjee, S. S., & Hill, M. D. (1998) · ACM SIGARCH Computer Architecture News · doi:10.1145/279361.279386 · Cited by 16
Online computation with untrusted advice
Angelopoulos, S., Dürr, C., Jin, S., Kamali, S., & Renault, M. P. (2024) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2024.103545 · Cited by 76
Makespan Minimization via Posted Prices
Feldman, M., Fiat, A., & Roytman, A. (2017) · ACM Conference on Economics and Computation (EC) · doi:10.1145/3033274.3085129 · Cited by 15
“Introduced in the context of self-adjusting search trees [35], paging, list update [34], and snoopy caching [27], there soon arose a vast host of online problems for which competitive analysis was applied.”
BackgroundOnline traveling salesman problem with deadline and advanced information
Wen, X., Xu, Y., & Zhang, H. (2012) · Computers & Industrial Engineering · doi:10.1016/j.cie.2012.07.003 · Cited by 15
Migrating and replicating data in networks
Bieńkowski, M. (2011) · Computer Science - Research and Development · doi:10.1007/s00450-011-0150-8 · Cited by 14
Non-additive two-option ski rental
Levi, A., & Patt-Shamir, B. (2015) · Theoretical Computer Science · doi:10.1016/j.tcs.2015.01.038 · Cited by 17
Boyar, J., Eidenbenz, S., Favrholdt, L. M., et al. (2018) · Algorithmica · doi:10.1007/s00453-018-0519-1 · Cited by 15
Online algorithms for prefetching and caching on parallel disks
Shah, R., Varman, P., & Vitter, J. S. (2004) · ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) · doi:10.1145/1007912.1007950 · Cited by 15
“See [18, 14 , 1, 10, 7] for some fundamental results for competitive online paging.”
BackgroundOn-Line Edge-Coloring with a Fixed Number of Colors
Favrholdt, L. M., & Nielsen, N. (2002) · Algorithmica · doi:10.1007/s00453-002-0992-3 · Cited by 15
“The Measures. To measure the quality of the algorithms, we use the competitive ratio which was introduced in [ 5 ] and has become a standard measure for on-line algorithms.”
MethodAlternative Measures for the Analysis of Online Algorithms
Dorrigiv, R. (2010) · UWSpace (University of Waterloo) · Cited by 16
Memory paging for connectivity and path problems in graphs
Feuerstein, E., & Marchetti-Spaccamela, A. (1993) · Lecture notes in computer science · doi:10.1007/3-540-57568-5_273 · Cited by 15
Lorenz, J. M. (2008) · Repository for Publications and Research Data (ETH Zurich) · doi:10.3929/ethz-a-005687539 · Cited by 14
Competitive Online Optimization under Inventory Constraints
Lin, Q., Yi, H., Pang, J., Chen, M., Wierman, A., Honig, M. L., & Xiao, Y. (2019) · Proceedings of the ACM on Measurement and Analysis of Computing Systems · doi:10.1145/3322205.3311081 · Cited by 36
“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].”
BackgroundMethodThe multi-shop ski rental problem
Ai, L., Wu, X., Huang, L., Huang, L., Tang, P., & Li, J. (2014) · ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS) · doi:10.1145/2591971.2591984 · Cited by 21
“[14], and then studied by Karlin’s seminal paper [13] which proposes a randomized algorithm and gives a e e−1 competitive ratio.”
BackgroundEvaluating the quality of online optimization algorithms by discrete event simulation
Dunke, F., & Nickel, S. (2016) · Central European Journal of Operations Research · doi:10.1007/s10100-016-0455-6 · Cited by 16
“Competitive analysis (Karlin et al. 1988; Sleator and Tarjan 1985) has become the standard for measuring online algorithm performance.”
BackgroundMethodOnline Energy Management in IoT Applications
Sehati, A., & Ghaderi, M. (2018) · doi:10.1109/infocom.2018.8486421 · Cited by 14
“EO’s design is motivated by the classic Ski-rental problem [12].”
BackgroundRandomized k-server algorithms for growth-rate bounded graphs
Bartal, Y., & Mendel, M. (2004) · Journal of Algorithms · doi:10.1016/j.jalgor.2004.06.002 · Cited by 18
Empirical studies of competitve spinning for a shared-memory multiprocessor
Karlin, A. R., Li, K., Manasse, M. S., et al. (1991) · ACM SIGOPS Operating Systems Review · doi:10.1145/121133.286599 · Cited by 14
Self-citationThe CNN Problem and Other k-Server Variants
Koutsoupias, E., & Taylor, D. S. (2000) · Lecture notes in computer science · doi:10.1007/3-540-46541-3_48 · Cited by 14
New results for online page replication
Fleischer, R., Głazek, W., & Seiden, S. S. (2004) · Theoretical Computer Science · doi:10.1016/j.tcs.2004.05.017 · Cited by 14
“, General Snoopy Caching [20]) are best described by the l1-model.”
BackgroundOptimal Scheduling for Wireless On-Demand Data Packet Delivery to High-Speed Trains
Chen, T., Shan, H., & Wang, X. (2014) · IEEE Transactions on Vehicular Technology · doi:10.1109/tvt.2014.2362912 · Cited by 13
List Factoring and Relative Worst Order Analysis
Ehmsen, M. R., Kohrt, J. S., & Larsen, K. S. (2012) · Algorithmica · doi:10.1007/s00453-012-9637-3 · Cited by 13
“The most standard performance measure for online algorithms is competitive analysis [20, 22, 28].”
BackgroundOn Energy Conservation in Data Centers
Albers, S. (2019) · ACM Transactions on Parallel Computing · doi:10.1145/3364210 · Cited by 15
“DPM for a single device with two states is equivalent to the ski-rental problem, a famous rent-or-buy problem [16, 17, 19, 22].”
BackgroundScheduling for on-line taxi problem on a real line and competitive algorithms
Xin, C., & Ma, W. (2005) · doi:10.1109/icmlc.2004.1378561 · Cited by 13
Price Fluctuations: To Buy or to Rent
Bieńkowski, M. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-12450-1_3 · Cited by 13
Seat reservation allowing seat changes
Boyar, J., Krarup, S., & Nielsen, M. N. (2004) · Journal of Algorithms · doi:10.1016/j.jalgor.2004.02.002 · Cited by 13
Application-Supported Device Management for Energy and Performance
Heath, T., Pinheiro, E., & Bianchini, R. (2003) · Lecture notes in computer science · doi:10.1007/3-540-36612-1_11 · Cited by 13
“deact +(P s+1 ·T s )+E s+1 act . The rationale for this assumption is similar to the famous competitive argument about renting or buying skis [ 10 ].”
BackgroundMOCA: A multiprocessor on-line competitive algorithm for real-time system scheduling
Koren, G., Shasha, D. E., & Huang, S. (2002) · Proceedings/Proceedings - Real-Time Systems Symposium · doi:10.1109/real.1993.393503 · Cited by 13
Customizing ML Predictions for Online AlgorithmsPreprint
Anand, K., Ge, R., & Panigrahi, D. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2205.08715 · Cited by 23
“It is well-known that the best competitive ratio achievable by a deterministic algorithm for this problem is 2 (e.g., [8]), and that by a randomized algorithm is e e − 1 (e.g., [1]).”
BackgroundPaging and list update under bijective analysis
Angelopoulos, S., & Schweitzer, P. (2013) · Journal of the ACM · doi:10.1145/2450142.2450143 · Cited by 12
“The resulting measure (termed competitive ratio in [ 21 ]) has led to the development of a mathematical theory of online algorithms (see [7] and [17] for a comprehensive treatment of the area).”
BackgroundResultSelf-Adaptive Linear Hashing for solid state drives
Yang, C., Jin, P., Yue, L., & Zhang, D. (2016) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2016.7498260 · Cited by 12
“The break-even [19] algorithm has been proven to be the best deterministic algorithm with a strong competitive ratio of 2.”
BackgroundIncreased axonal transport of trigeminal ganglion proteins in an electrode model.
Chan, K. Y., Beck, T. W., Mullen, P., & Dong, W. K. (1989) · PubMed · doi:10.5555/2095116.2095248 · Cited by 13
Venanzi, R., Foschini, L., Bellavista, P., Kantarcı, B., & Stefanelli, C. (2019) · IEEE Access · doi:10.1109/access.2019.2938888 · Cited by 14
“The authors in [35], demonstrate that this problem is 2-competitive.”
BackgroundThe Advice Complexity of a Class of Hard Online Problems
Boyar, J., Favrholdt, L. M., Kudahl, C., et al. (2016) · Theory of Computing Systems · doi:10.1007/s00224-016-9688-y · Cited by 12
“Definition 1 (Competitive ratio [23, 32] and advice complexity [7, 22]) The input to an online problem, P, is a request sequence σ = 〈r1, .”
BackgroundSystem level online power management algorithms
Ramanathan, D., & Gupta, R. K. (2002) · Design, Automation, and Test in Europe · doi:10.1109/date.2000.840847 · Cited by 12
“The analysis in this section builds upon the work of Karlin, Manasse, Rudolph and Sleator [5], and speci cally their formulation of the spin block problem [4].”
MethodInfluentialOn the performance of competitive algorithms in practice
Karlin, A. R. (1998) · Lecture notes in computer science · doi:10.1007/bfb0029577 · Cited by 13
“1 This analogy was originally suggested by Larry Rudolph in the context of the work on competitive snoopy caching [ 16 ].”
BackgroundSelf-citationNew Results for Online Page Replication
Fleischer, R., & Seiden, S. S. (2000) · Lecture notes in computer science · doi:10.1007/3-540-44436-x_15 · Cited by 12
Khanna, S., & Liberatore, V. (1998) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/276698.276879 · Cited by 12
“Thus, any strongly competitive paging algorithm, e.g., the marking algorithm [ 13 ], is trivially (k(n − 1))-competitive for broadcast disk paging even against a ubiquitous adversary.”
BackgroundResultInfluentialA New Approach to Online Scheduling
Lübbecke, E., Maurer, O., Megow, N., et al. (2016) · ACM Transactions on Algorithms · doi:10.1145/2996800 · Cited by 11
“Competitive analysis [Sleator and Tarjan 1985; Karlin et al. 1988] is the most popular method for studying the performance of online algorithms.”
MethodEnergy-delay tradeoff for request bundling on smartphones
Sehati, A., & Ghaderi, M. (2017) · doi:10.1109/infocom.2017.8057063 · Cited by 11
“Inspired by the classic Ski Rental problem [20], we design a deterministic online algorithm for EnerB called the Break-Even algorithm (BE).”
MethodOn the Best Possible Competitive Ratio for Multislope Ski Rental
Fujiwara, H., Kitano, T., & Fujito, T. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-25591-5_56 · Cited by 12
“, 2-slope) ski-rental problem [KMRS88] was first introduced in the context of snoopy caching.”
BackgroundInfluentialExploiting Staleness for Approximating Loads on CMPs
Rengasamy, P. V., Sivasubramaniam, A., Kandemir, M., et al. (2015) · doi:10.1109/pact.2015.27 · Cited by 11
“, [1], [2], [3]), relaxed consistency models have also been proposed (e.”
BackgroundFormal Analysis of Online Algorithms
Aminof, B., Kupferman, O., & Lampert, R. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-24372-1_16 · Cited by 11
Price Fluctuation in Online Leasing
Feldkord, B., Markarian, C., & der Heide, F. M. A. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-71147-8_2 · Cited by 11
Randomized Online Scheduling with Delivery Times
Seiden, S. (1999) · Journal of Combinatorial Optimization · doi:10.1023/a:1009875403874 · Cited by 11
Martin, M. M. K., Harper, P. J., Sorin, D. J., et al. (2004) · Proceedings - International Symposium on Computer Architecture/Proceedings · doi:10.1109/isca.2003.1207001 · Cited by 11
“Other hybrid protocols adapt between writeinvalidate and write-update [4, 9, 15, 26, 31], by migrating data near to where it is being used [10, 14, 35] or by adapting to available bandwidth [24].”
BackgroundAdaptability and the Usefulness of Hints (Extended Abstract)
Berman, P., & Garay, J. A. (1998) · Lecture notes in computer science · doi:10.1007/3-540-68530-8_23 · Cited by 11
“The \classical" competitive analysis [21, 18 ] is essentially worst-case analysis applied to the case of on-line computations.”
MethodSynchronization with multiprocessor caches
Lee, J., & Ramachandran, U. (2002) · Proceedings - International Symposium on Computer Architecture/Proceedings · doi:10.1109/isca.1990.134504 · Cited by 11
Online bin covering: Expectations vs. guarantees
Christ, M. G., Favrholdt, L. M., & Larsen, K. S. (2014) · Theoretical Computer Science · doi:10.1016/j.tcs.2014.06.029 · Cited by 13
“k (DHk), uses exactly jitems from the interval [1 j , 1 j−1) to cover a bin. All through the paper we assume that k≥ 2, since for k= 1, DHk becomes DNF. 2 Competitive Analysis In competitive analysis [24, 19], the performance of an online algorithm is compared to that of an optimal offline algorithm Opt. An algorithm Af…”
MethodAlgorithmic Approaches for a Dependable Smart Grid
Bein, W. W., Madan, B. B., Bein, D., & Nyknahad, D. (2016) · Advances in intelligent systems and computing · doi:10.1007/978-3-319-32467-8_59 · Cited by 10
On bin packing with clustering and bin packing with delays
Epstein, L. (2021) · Discrete Optimization · doi:10.1016/j.disopt.2021.100647 · Cited by 19
“ld find a trade-off between waiting for additional items to arrive and the resulting delay costs of already existing items, and one expects to see algorithms designed based on ski-rental type methods 2 [24, 22, 21]. Such methods involve waiting until a certain cost is incurred before performing an action that stops the…”
MethodThe Distributedk-Server Problem—A Competitive Distributed Translator fork-Server Algorithms
Bartal, Y., & Rosén, A. (1997) · Journal of Algorithms · doi:10.1006/jagm.1996.0826 · Cited by 10
Polynomial-Time Approximation Schemes for Shortest Path with Alternatives
Nonner, T. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-33090-2_65 · Cited by 10
Distributed online frequency assignment in cellular networks
Janssen, J., Kriz̧anc, D., Narayanan, L., et al. (1998) · Lecture notes in computer science · doi:10.1007/bfb0028544 · Cited by 10
Page migration with limited local memory capacity
Albers, S., & Koga, H. (1995) · Lecture notes in computer science · doi:10.1007/3-540-60220-8_58 · Cited by 12
“From a theoretical point of view they were studied only once before in [9].”
BackgroundScheduling Jobs on Grid Processors
Boyar, J., & Favrholdt, L. M. (2008) · Algorithmica · doi:10.1007/s00453-008-9257-0 · Cited by 10
“The standard measure for the quality of on-line algorithms is the competitive ratio [11, 13], which is the worst-case ratio of the on-line performance to the optimal offline performance, up to an additive constant.”
BackgroundOptimal Read-Once Parallel Disk Scheduling
Kallahalla, M., & Varman, P. (2005) · Algorithmica · doi:10.1007/s00453-004-1129-7 · Cited by 10
Connection caching under various models of communication
Cohen, E., Kaplan, H. Y., & Zwick, U. (2000) · ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) · doi:10.1145/341800.341808 · Cited by 10
“Furthermore,wealso showthatatype-2markingalgorithmcalledFWF,whichis derivedfromthesingle-cachealgorithmFWF(FlushWhen Full)[10]isalsok-competitive.”
MethodJitter control in QoS networks
Mansour, Y., & Patt-Shamir, B. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1998.743428 · Cited by 10
“Algorithms whose performance can be bounded with respect to the performance of an off-line adversary are called competitive [10], [ 7 ], [1].”
BackgroundDynamic TCP acknowledgment in the LogP model
Frederiksen, J. S., Larsen, K. S., Noga, J., et al. (2003) · Journal of Algorithms · doi:10.1016/s0196-6774(03)00058-0 · Cited by 10
On Algorithm Design for Metrical Task Systems
Burley, W. R., & Irani, S. (1997) · Algorithmica · doi:10.1007/pl00009166 · Cited by 10
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.