Competitive randomized algorithms for nonuniform problems
The DOI matches its Crossref record; 19 of the 19 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
“As is well known, the best possible online strategy for classical ski rental has competitive ratio of e e 1 ≈ 1 . 582.”
From Rent, Lease, or Buy: Randomized Algorithms for Multislope Ski Rental (2012) · cites this paper as [10]
In the citing paper
“Karlin et al. [12] designed a randomized algorithm that yields a competitive ratio of e e -1 ≈ 1 . 58 , which is also optimal.”
From Improving Online Algorithms via ML Predictions (2024) · cites this paper as [12]
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
Karlin, A. R., Manasse, M. S., Rudolph, L., & Sleator, D. D. (1988) · Algorithmica · doi:10.1007/bf01762111 · Cited by 631 · cited 3×
“Thus the deterministic algorithm of Karlin et al. [ 14 ] is also optimally competitive against this adversary.”
MethodInfluentialSelf-citationFiat, 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 · cited 3×
“A large number of problems have been studied from this point of view, see [1]-[8] and [ 10 ]-[20].”
BackgroundResultInfluentialSelf-citationCompetitive 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 · cited 3×
“For an explanation, see [ 16 ].) Laziness implies that 0 < nl <_ "'" < n2a-i <- nza = 1. Competitive Randomized Algorithms for Nonuniform Problems 565”
BackgroundMethodInfluentialSelf-citationAn 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
On 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
A strongly competitive randomized paging algorithm
McGeoch, L. A., & Sleator, D. D. (1991) · Algorithmica · doi:10.1007/bf01759073 · Cited by 238 · cited 2×
“They also described an algorithm that is 2Hk-competitive for all k. McGeoch and Sleator [ 18 ] later obtained an H kcompetitive algorithm for all k.”
BackgroundMethodSelf-citationNew 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
An optimal online algorithm for metrical task systems
Borodin, A., Linial, N., & Saks, M. (1987) · Proceedings of the nineteenth annual ACM conference on Theory of computing - STOC '87 · doi:10.1145/28395.28435 · Cited by 164
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
Research works printed but not linked: 1
- McGeoch, L. A. Algorithms for Two Graph Problems. Ph.D. thesis, Carnegie Mellon University, 1987.
Cited by
Items 201–258 of 258
The 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
A Learning-Augmented Algorithm for the Parking Permit Problem with Three Permit Types
Yaroslav, K., & Kononov, A. V. (2024) · Lecture notes in computer science · doi:10.1007/978-3-031-62792-7_8 · Cited by 1
Efficient unlearning for data security in deep learning systems
Guo, E., Su, C., & Li, P. (2025) · The Computer Journal · doi:10.1093/comjnl/bxaf031 · Cited by 1
Resource Cost Aware Scheduling Problems
Carrasco, R. A. (2013) · doi:10.7916/d8z60wdx · Cited by 1
Adaptive power management with fine-grained delay constraints
Wu, K., Liu, Y., Zhang, H., & Qian, D. (2010) · IEEE International Conference on Computer Science and Information Technology · doi:10.1109/iccsit.2010.5565140 · Cited by 1
Metrical Service Systems with Multiple Servers
Chiplunkar, A., & Vishwanathan, S. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-38768-5_43 · Cited by 1
An Optimal Power Management for Stationary Multiprocessor Systems
Sun, W., & Sugawara, T. (2011) · International Conference on Networking and Computing · doi:10.1109/icnc.2011.29 · Cited by 1
Energy management in real-time multi-tier internet services
Kevin Skadron, Y., & Horváth, T. (2008) · Cited by 1
A Lazy Approach to Online Learning with Constraints.
Kveton, B., Yu, J. Y., Theocharous, G., & Mannor, S. (2008) · Cited by 1
Hybrid Power Management for Office Equipment
Gingade, G., Chen, W., Lu, Y.-H., Allebach, J., & Gutierrez-Vazquez, H. I. (2016) · ACM Transactions on Design Automation of Electronic Systems · doi:10.1145/2910582 · Cited by 1
Energy Optimization in Cryptographic Protocols for the Cloud
Roy, S., Ahuja, S. P., Harish, P. D., & Talluri, S. R. (2018) · Advances in computer and electrical engineering book series · doi:10.4018/978-1-5225-4044-1.ch002 · Cited by 1
NFV-Based Distributed Service Function Chaining with Imperfect Information
Alikhani, M., Sheikhi, M., & Hakami, V. (2021) · International Conference on Information and Knowledge Technology (IKT) · doi:10.1109/ikt54664.2021.9685058 · Cited by 1
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
Using Online Algorithms to Solve NP-Hard Problems
Kumar, A., & Yadav, R. K. P. (2024) · International Journal of Innovative Science and Research Technology (IJISRT) · doi:10.38124/ijisrt/ijisrt24oct247 · Cited by 1
Damaschke, P. (2002) · Theoretical Computer Science · doi:10.1016/s0304-3975(01)00289-4 · Cited by 1
To Wait or Not to Wait? Analysis for the Traveler's Waiting Problem with Incomplete Information
Wang, K., Liu, J. N. K., & Ma, W. (2008) · Networked Computing and Advanced Information Management · doi:10.1109/ncm.2008.16 · Cited by 1
Context-Aware Power Management
Harris, C. (2006) · Cited by 1
Implementation of Algorithms for Right-Sizing Data CentersPreprint
Hübotter, J. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2108.09489 · Cited by 1
Optimizing Timeout-Based Sleep Algorithms
Markopoulou, A. P., & Bambos, N. (2005)
Online Vertex Cover and Matching: Beating the Greedy AlgorithmPreprint
Wang, Y., & Wong, S. C.-W. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1305.1694
Fair Scheduling of General-Purpose Workloads on Workstation Clusters
Anglano, C. (2002) · Cluster Computing · doi:10.1023/a:1012752923793
Mohr, E. (2011) · Publications of the UdS (Saarland University) · doi:10.22028/d291-26157
Zhang, Y. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1504.05305
Rent or Buy Problems with a Fixed Time Horizon
Epstein, L., & Zebedat-Haider, H. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-40313-2_33
Online Power-Managing Strategy with Hard Real-Time GuaranteesPreprint
Chen, J.-J., Kao, M.-J., Lee, D. T., Rutter, I., & Wagner, D. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1304.1590
ON THE USE OF COSCHEDULING IN FAST COMMUNICATION SYSTEMS
Chiola, G., Ciaccio, G., & Anglano, C. (2001) · Parallel Processing Letters · doi:10.1142/s0129626401000543
Proper Framework for the Application of Power Management Algorithms
Thanos, G. A., & Stassinopoulos, G. I. (2004) · Design Automation for Embedded Systems · doi:10.1007/s10617-005-1197-1
Damaschke, P. (2005) · Algorithmica · doi:10.1007/s00453-005-1163-0
Balancing disk energy against reliability in video playback
Song, M., Ryu, W., Sim, J. S., & Lee, Y. (2013) · Multimedia Systems · doi:10.1007/s00530-013-0305-5
Optimizing energy consumption under flow and stretch constraints
Zhang, Z., & Li, F. (2011) · IEEE International Performance, Computing, and Communications Conference · doi:10.1109/pccc.2011.6108076
IT service level agreements based on the optimal strategies
Yang, H. (2009) · IEEE International Conference on Grey systems and Intelligent Services · doi:10.1109/gsis.2009.5408028
Cash Management and Its Risk Control under No-Stationary Uncertain Demand
Liu, B., Wentian, C., & Chunlin, X. (2008) · International Symposium on Electronic Commerce and Security · doi:10.1109/isecs.2008.87
Performance of Switch Blocking on Multithreaded Architectures
Gopinath, K., M.k., K. N., Lim, B.-H., & Agarwal, A. (1994) · Proceedings of the International Conference on Parallel Processing · doi:10.1109/icpp.1994.161
A Gradient Learning Optimization for Dynamic Power Management
Li, Y., & Jiang, F. (2015) · Conference proceedings/Conference proceedings - IEEE International Conference on Systems, Man, and Cybernetics · doi:10.1109/smc.2015.360
Energy-Efficient Monitoring and Controlling of Computer Systems
Berge, M. V. D., & Christmann, W. (2012) · IGI Global eBooks · doi:10.4018/978-1-4666-2190-9.ch006
Damaschke, P. (2000) · Lecture notes in computer science · doi:10.1007/3-540-46521-9_6
Analysis of Power-Down Systems with Five States
Pathak, G. (2016) · Digital Scholarship - UNLV (University of Nevada Reno) · doi:10.34917/9112163
Competitive algorithms for online matching and vertex cover problems
Wong, C. W. (2013) · DSpace@MIT (Massachusetts Institute of Technology)
Reducing Energy Consumption and Latency of Applications on Wireless Devices
Sehati, A. (2018) · Libraries and Cultural Resources (University of Calgary) · doi:10.11575/prism/13062
Cost-aware VNF placement in cloud infrastructures
Ghrada, N. (2018) · Espace ÉTS (ETS)
Online Balanced RepartitioningPreprint
Avin, C., Loukas, A., Pacut, M., & Schmid, S. (2015) · arXiv (Cornell University)
Huang, T., Tsao, S., Wu, L.-C., Chu, E. T.-H., & Liu, K. (2007) · Springer eBooks · doi:10.1007/1-4020-5352-5_5
Quantitative Comparison of Power Management Algorithms
Lu, Y.-H., Chung, E.-Y., Simunic, T., Benini, L., & Micheli, G. D. (2008) · Design, Automation, and Test in Europe · doi:10.1007/978-1-4020-6488-3_16
Manasse, M. S. (2014) · Springer eBooks · doi:10.1007/978-3-642-27848-8_378-2
Self-citationManasse, M. S. (2016) · Springer eBooks · doi:10.1007/978-1-4939-2864-4_378
Self-citationPatt-Shamir, B., & Yadai, E. (2023) · Theory of Computing Systems · doi:10.1007/s00224-023-10126-y
MPMD on Two Sources with Lookahead
Sun, E., Wang, B., Xue, Q., Zhao, M., & Zhu, Z. (2025) · Lecture notes in computer science · doi:10.1007/978-981-96-1090-7_15
Group Rent-or-Buy: the Benefits of Having Grouped Consumers
Meng, L.-Y., Wang, C., & Ye, Q. (2025) · Journal of the Operations Research Society of China · doi:10.1007/s40305-025-00590-3
Το άμεσο πρόβλημα ελάχιστου αθροίσματος κάλυψης συνόλου
Vardas, E. (2020) · DSpace - NTUA (National Technical University of Athens) · doi:10.26240/heal.ntua.17414
ONLINE RESOURCE RESERVATION FORMOBILE EDGE COMPUTING SERVICES
Zang, S. (2021) · The Sydney eScholarship Repository (The University of Sydney)
Understanding Cross-Cloud Interconnects: Hands-On Measurements and Cost Optimization
Eliav, E., Keslassy, I., Breitgand, D., Lorenz, D. H., & Weit, A. (2026) · IEEE ... International Conference on Cloud Computing · doi:10.1109/cloud72782.2026.00024
“The ski-rental problem is a foundational online problem that models the trade-off between an ongoing rental cost and a one-time purchase cost, under uncertainty about the future [44], [45].”
Group Commit Self-Clocks: Why Tuning Is Unnecessary Above a Device-Set Load ThresholdPreprint
Mandarapu, M., & Kunkunuru, S. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2606.18187
“…periodic timer is F 0 / ( λT ) + T/ 2, minimized at the EOQ square-root rule T ⋆ = 2 F 0 /λ ; and the wait-or-flush decision is the rent-or-buy / ski-rental problem [Karlin et al., 1994], equivalently the dynamic-TCP-acknowledgment problem [Dooly et al., 2001], which is 2-competitive deterministic.”
Primal-Dual Online Algorithms for the Parking Permit ProblemPreprint
Coester, C., & Turoczy, A. (2026) · arXiv (Cornell University) · doi:10.4230/lipics.esa.2026.81
“For this problem, the competitive ratio is 2 for deterministic algorithms, and e/ ( e − 1) for randomized algorithms [20].”
Competitive analysis of the online leasing problem with a piecewise price function
Chen, X., & Ma, W. (2026) · Journal of Optimization Theory and Applications · doi:10.1007/s10957-026-03062-7
“…expected competitive ratio is The randomized algorithms respectively are From Theorem 2, we note that when λ = b r , we can deduce that which is the same as the conclusion presented in [18]. is the optimal randomized strategy, where t ∗ = b + r λ − a λ r , and the optimal competitive ratio is c ∗ 3”
Risk-Sensitive Peak-Aware Energy Scheduling: Competitive and Learning-Augmented Algorithms
Himmelreich, L., Christianson, N., & Wierman, A. (2026) · ACM SIGMETRICS Performance Evaluation Review · doi:10.1145/3848038.3848064
“A key technique for improving performance in such online problems is randomization, which enables improved bounds in the Bahncard problem and many other online problems [11, 13, 9, 4, 5].”
Metadata
- Authors
- Karlin, A. R., Manasse, M. S., McGeoch, L. A., & Owicki, S.
- Affiliations
- Amherst College (US)
- Venue
- Algorithmica
- Published
- 1994-06
- Volume
- 11
- Issue
- 6
- Pages
- 542-571
- ISSN
- 0178-4617 (ISSN-L)
- 1432-0541
- OpenAlex
- W3137684744
- Cited by
- 258
- References
- 19
- Citations by year
- 2026: 4 · 2025: 7 · 2024: 10 · 2023: 5 · 2022: 8 · 2021: 10 · 2020: 11 · 2019: 8 · 2018: 11 · 2017: 9 · 2016: 8 · 2015: 9 · 2014: 12 · 2013: 10 · 2012: 10
- FWCI
- 2.88
- 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 › Mathematics › Theoretical Computer Science › Algorithms and Data Compression
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Keywords
- competitive analysis, randomized online algorithms, oblivious adversary, adaptive algorithms, request sequences, performance ratio, isosceles triangles
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.