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 101–200 of 258
The 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
Scalable Power Management Using Multilevel Reinforcement Learning for Multiprocessors
Pan, G.-Y., Jou, J.-Y., & Lai, B.-C. C. (2014) · ACM Transactions on Design Automation of Electronic Systems · doi:10.1145/2629486 · Cited by 15
Subscription or Pay-as-You-Go: Optimally Purchasing IaaS Instances in Public Clouds
Yang, S., Pan, L., Wang, Q., Liu, S., & Zhang, S. (2018) · IEEE International Conference on Web Services (ICWS) · doi:10.1109/icws.2018.00035 · Cited by 15
Competitive Algorithms for Online Leasing Problem in Probabilistic Environments
Xu, Y., & Xu, W. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-28648-6_116 · Cited by 15
A General Decomposition Theorem for the k-Server Problem
Seiden, S. S. (2001) · Lecture notes in computer science · doi:10.1007/3-540-44676-1_7 · Cited by 15
A Homogeneous Architecture for Power Policy Integration in Operating Systems
Pettis, N., & Lu, Y.-H. (2008) · IEEE Transactions on Computers · doi:10.1109/tc.2008.180 · Cited by 14
Adaptive timeout policies for fast fine-grained power management
Kveton, B., Gandhi, P., Theocharous, G., Mannor, S., Rosario, B., & Shah, N. (2007) · Cited by 14
Maximizing the Profit of Cloud Broker with Priority Aware Pricing
Wang, X., Wu, S., Wang, K., Di, S., Jin, H., Yang, K., & Ou, S. (2017) · IEEE International Conference on Parallel and Distributed Systems (ICPADS) · doi:10.1109/icpads.2017.00073 · Cited by 14
An Online Model for Managing Cash: An Alternative Approach to the Miller-Orr Model
Liu, B., & Xin, C. (2008) · International Conference on Natural Computation (ICNC) · doi:10.1109/icnc.2008.310 · Cited by 13
Khan, U. A., & Rinner, B. (2012) · IEEE International Conference on Internet of Things (iThings) and IEEE Green Computing and Communications (GreenCom) and IEEE Cyber, Physical and Social Computing (CPSCom) and IEEE Smart Data (SmartData) · doi:10.1109/greencom.2012.85 · Cited by 13
Power-Aware Resource Management Techniques for Low-Power Embedded Systems
Kim, J., & Simunic, T. (2007) · Chapman & Hall/CRC computer and information science series · doi:10.1201/9781420011746.ch6 · Cited by 13
SOAR: Smart Online Aggregated Reservation for Mobile Edge Computing Brokerage Services
Zang, S., Bao, W., Yeoh, P. L., Vucetic, B. S., & Li, Y. (2021) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2021.3075947 · Cited by 13
Coskun, A. K., Strong, R. D., Tullsen, D. M., & Simunic, T. (2009) · ACM SIGMETRICS Performance Evaluation Review · doi:10.1145/2492101.1555369 · 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
Dynamic power management of laptop hard disk (poster paper)
Simunic, T., Benini, L., Glynn, P. W., & Micheli, G. D. (2000) · Design, Automation, and Test in Europe · doi:10.1145/343647.344103 · Cited by 13
On the performance of competitive algorithms in practice
Karlin, A. R. (1998) · Lecture notes in computer science · doi:10.1007/bfb0029577 · Cited by 13
Self-citationUsing stochastic intervals to predict application behavior on contended resources
Schopf, J. M., & Berman, F. (2003) · International Symposium on Pervasive Systems, Algorithms and Networks (ISPAN) · doi:10.1109/ispan.1999.778962 · Cited by 13
Self-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
“Karlin et al. [21] first presented this algorithm with distribution i π (see Formula 4).”
BackgroundAn Online Algorithm for Selling Your Reserved IaaS Instances in Amazon EC2 Marketplace
Yang, S., Pan, L., & Liu, S. (2019) · IEEE International Conference on Web Services (ICWS) · doi:10.1109/icws.2019.00057 · Cited by 12
Selling Reserved Instances through Pay-as-You-Go Model in Cloud Computing
Zhang, S., Yuan, D., Pan, L., Liu, S., Cui, L., & Meng, X. (2017) · IEEE International Conference on Web Services (ICWS) · doi:10.1109/icws.2017.25 · Cited by 12
Venanzi, R., Foschini, L., Bellavista, P., Kantarcı, B., & Stefanelli, C. (2019) · IEEE Access · doi:10.1109/access.2019.2938888 · Cited by 14
Optimal Online Balanced Graph Partitioning
Pacut, M., Parham, M., & Schmid, S. (2021) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infocom42981.2021.9488824 · Cited by 12
“In Section III-A, we show an O(k · `)-competitive algorithm for k = 3 using the classic rent-or-buy approach [30].”
MethodOnline dynamic power management with hard real-time guarantees
Chen, J.-J., Kao, M.-J., Lee, D.-H., Rutter, I., & Wagner, D. (2015) · Theoretical Computer Science · doi:10.1016/j.tcs.2015.06.014 · Cited by 12
Automatic Run-Time Selection of Power Policies for Operating Systems
Pettis, N., Ridenour, J., & Lu, Y.-H. (2006) · Design, Automation, and Test in Europe · doi:10.1109/date.2006.243860 · Cited by 12
A General Decomposition Theorem for the k-Server Problem
Seiden, S. S. (2002) · Information and Computation · doi:10.1006/inco.2002.3144 · Cited by 12
A cost-driven online auto-scaling algorithm for web applications in cloud environments
Si, W., Pan, L., & Liu, S. (2022) · Knowledge-Based Systems · doi:10.1016/j.knosys.2022.108523 · Cited by 11
On 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
Power Management for Stationary Machines in a Pervasive Computing Environment
Harris, C., & Cahill, V. (2005) · Hawaii International Conference on System Sciences (HICSS) · doi:10.1109/hicss.2005.499 · Cited by 11
A randomized on–line algorithm for thek–server problem on a line
Csaba, B., & Lodha, S. (2006) · Random Structures and Algorithms · doi:10.1002/rsa.20124 · Cited by 11
“[22] showed matching upper and lower bounds of e e−1 .”
BackgroundRandomized Online Scheduling with Delivery Times
Seiden, S. (1999) · Journal of Combinatorial Optimization · doi:10.1023/a:1009875403874 · Cited by 11
Fast randomized algorithm with restart strategy for minimal test cost feature selection
Li, J., Zhao, H., & Zhu, W. (2014) · International Journal of Machine Learning and Cybernetics · doi:10.1007/s13042-014-0262-0 · Cited by 10
Algorithmic 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
Interval Job Scheduling With Machine Launch Cost
Ren, R., Zhu, Y., Li, C., & Tang, X. (2020) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2020.3002786 · Cited by 10
To Sell or Not To Sell: Trading Your Reserved Instances in Amazon EC2 Marketplace
Yang, S., Pan, L., Wang, Q., & Liu, S. (2018) · IEEE International Conference on Distributed Computing Systems (ICDCS) · doi:10.1109/icdcs.2018.00095 · Cited by 10
Benini, L., Bogliolo, A., & Micheli, G. D. (2002) · Elsevier eBooks · doi:10.1016/b978-155860702-6/50020-x · Cited by 10
On-Line Algorithms and the k-Server Conjecture
Koutsoupias, E. (1994) · doi:10.12681/eadd/10816 · Cited by 10
On the Advice Complexity of the k-server Problem Under Sparse Metrics
Gupta, S., Kamali, S., & López-Ortíz, A. (2015) · Theory of Computing Systems · doi:10.1007/s00224-015-9649-x · Cited by 9
Caching or re-computing: Online cost optimization for running big data tasks in IaaS clouds
Fu, X., Pan, L., & Liu, S. (2024) · Journal of Network and Computer Applications · doi:10.1016/j.jnca.2024.104080 · Cited by 9
Randomized algorithms for metrical task systems
Irani, S., & Seiden, S. (1995) · Lecture notes in computer science · doi:10.1007/3-540-60220-8_59 · Cited by 9
Backup or Not: An Online Cost Optimal Algorithm for Data Analysis Jobs Using Spot Instances
Lin, L., Pan, L., & Liu, S. (2020) · IEEE Access · doi:10.1109/access.2020.3014978 · Cited by 11
“Our backup problem can be seen as an analogy to the classical rent-or-buy problems including Bahncard problem [30], ski board rental problem [31], TCP acknowledgment problem [32] and so on.”
A Random Online Algorithm for Reselling Reserved IaaS Instances in Amazon's Cloud Marketplace
Xie, Y., Pan, L., Yang, S., & Liu, S. (2022) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2021.3138932 · Cited by 10
The multi-shop ski rental problem
Ai, L., Wu, X., Huang, L., Huang, L., Tang, P., & Li, J. (2014) · ACM SIGMETRICS Performance Evaluation Review · doi:10.1145/2637364.2591984 · Cited by 10
A Better bound of randomized algorithms for the multislope ski-rental problem
Hu, M., & Xu, W. (2017) · RAIRO - Theoretical Informatics and Applications · doi:10.1051/ita/2017009 · Cited by 9
“This problem in continuous time case is discussed by Karlin et al. [5, 6] as following.”
BackgroundProbability-Based Online Algorithm for Switch Operation of Energy Efficient Data Center
Sun, J., Yang, Q., & Yang, Z. (2019) · IEEE Transactions on Cloud Computing · doi:10.1109/tcc.2019.2931961 · Cited by 7
Buying a Constant Competitive Ratio for Paging
Csirik, J., Imreh, C., Noga, J., Seiden, S., & Woeginger, G. J. (2001) · Lecture notes in computer science · doi:10.1007/3-540-44676-1_8 · Cited by 7
Improved Learning-Augmented Algorithms and (Tight) Lower Bounds for Multi-Option Ski Rental Problem
Shin, Y.-H., Lee, C., Lee, G., & An, H.-C. (2025) · ACM Transactions on Algorithms · doi:10.1145/3763239 · Cited by 11
“…the rent-or-buy case, where we only have two options ( 𝑑 1 ,𝑐 1 ) = ( 1 , 1 ) and ( 𝑑 2 ,𝑐 2 ) = (∞ , 𝐵 ) , was extensively studied both under the classical competitive analysis setting without learning augmentation [13, 25, 26] and the learning-augmented settings [4, 10, 11, 18, 29, 43].”
An Online Algorithm Optimally Self-tuning to Congestion for Power Management Problems
Bein, W. W., Hatta, N., Hernandez-Cons, N., Ito, H., Kasahara, S., & Kawahara, J. I. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-29116-6_4 · Cited by 6
Stochastization of Weighted Automata
Avni, G., & Kupferman, O. (2015) · Lecture notes in computer science · doi:10.1007/978-3-662-48057-1_7 · Cited by 6
Randomized Competitive Analysis for Two Server Problems
Bein, W. W., Iwama, K., & Kawahara, J. I. (2008) · Algorithms · doi:10.3390/a1010030 · Cited by 6
A MAC layer power management scheme for efficient energy delay tradeoff in a WLAN
Sarkar, M., & Cruz, R. L. (2007) · Computer Networks · doi:10.1016/j.comnet.2007.04.018 · Cited by 6
Online Algorithms for Multi-shop Ski Rental with Machine Learned Predictions
Wang, S., & Li, J. (2020) · Adaptive Agents and Multi-Agents Systems · doi:10.65109/ocnn5096 · Cited by 6
Manasse, M. S. (2008) · Encyclopedia of Algorithms · Cited by 6
Self-citationRisk-Sensitive Online Algorithms
Christianson, N., Sun, B., Low, S. H., & Wierman, A. (2024) · ACM SIGMETRICS Performance Evaluation Review · doi:10.1145/3695411.3695415 · Cited by 5
“Randomness can improve decision-making performance in many online problems; for instance, randomization improves the competitive ratio of online ski rental from 2 to − 1 [10] and of online search from polynomial to logarithmic in the fluctuation ratio [6].”
An Improved Algorithm for Online Min-Sum Set Cover
Bieńkowski, M., & Mucha, M. (2023) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v37i6.25835 · Cited by 5
Randomized Algorithm for MPMD on Two Sources
He, K., Li, S., Sun, E., Wang, Y., Wattenhofer, R. P., & Zhu, W. (2023) · Lecture notes in computer science · doi:10.1007/978-3-031-48974-7_20 · Cited by 5
Durand, J.-B., Girard, S., Ciriza, V., & Donini, L. (2012) · Journal of the Royal Statistical Society Series C (Applied Statistics) · doi:10.1111/j.1467-9876.2012.01053.x · Cited by 5
Competitive Analysis for Online Leasing Problem with Compound Interest Rate
Yang, X., Zhang, W.-G., Xu, W., & Zhang, Y. (2011) · Abstract and Applied Analysis · doi:10.1155/2011/156254 · Cited by 5
Online learning with expert advice and finite-horizon constraints
Kveton, B., Yu, J. Y., Theocharous, G., & Mannor, S. (2008) · Cited by 5
Dasgupta, A., Kumar, R., & Sarlós, T. (2017) · International World Wide Web Conference (WWW) · doi:10.1145/3041021.3054187 · Cited by 5
“We assume a generic online algorithm B for the two-state metrical task system problem (e.g., an algorithm for the ski-rental problem [18]).”
MethodCombinatorial Ski Rental and Online Bipartite Matching
Zhang, H., & Conitzer, V. (2020) · ACM Conference on Economics and Computation (EC) · doi:10.1145/3391403.3399470 · Cited by 5
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
Randomized online multi-threaded paging
Seiden, S. S. (1998) · Lecture notes in computer science · doi:10.1007/bfb0054374 · Cited by 5
Combinatorial algorithms for scheduling jobs to minimize server usage time
Ren, R. (2018) · doi:10.32657/10220/46906 · Cited by 5
Dim Silicon and the Case for Improved DVFS PoliciesPreprint
Gottschlag, M., Khalil, Y., & Bellosa, F. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2005.01498 · Cited by 5
Online Directed Spanners and Steiner ForestsPreprint
Grigorescu, E., Lin, Y., & Quanrud, K. (2021) · arXiv (Cornell University) · doi:10.4230/lipics.approx/random.2021.5 · Cited by 5
Manasse, M. S. (2008) · Springer eBooks · doi:10.1007/978-0-387-30162-4_378 · Cited by 5
Self-citationA simple deterministic algorithm for guaranteeing the forward progress of transactions
Leiserson, C. E. (2015) · Information Systems · doi:10.1016/j.is.2015.10.013 · Cited by 4
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
Liu, S., Pan, L., Liu, S., & Qi, K. (2024) · IEEE Internet of Things Journal · doi:10.1109/jiot.2024.3515208 · Cited by 4
“Competitive analysis is a common method used to evaluate the performance of online algorithms [27].”
A Task-Specific Approach to Dynamic Device Power Management for Embedded System
Yue, Z. (2006) · International Conference on Embedded Software and Systems · doi:10.1109/icess.2005.12 · Cited by 4
Bounds for the Multislope Ski-Rental Problem
Fujiwara, H., SHIBUSAWA, K., Yamamoto, K., & Yamamoto, H. (2020) · IEICE Transactions on Information and Systems · doi:10.1587/transinf.2019fcp0001 · Cited by 4
Patt-Shamir, B., & Yadai, E. (2020) · ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) · doi:10.1145/3350755.3400280 · Cited by 6
Machine Learning Advised Ski Rental Problem with a Discount
Bhattacharya, A., & Das, R. (2022) · Lecture notes in computer science · doi:10.1007/978-3-030-96731-4_18 · Cited by 5
Research on the IT service cost model
Yang, H., & Bai, Q. (2010) · International Conference on Networking and Digital Society (ICNDS) · doi:10.1109/icnds.2010.5479356 · Cited by 4
To transmit or not to transmit: an investigation using competitive analysis
Chandramouli, R., & Uma, R. N. (2004) · IEEE Wireless Communications and Networking Conference · doi:10.1109/wcnc.2003.1200486 · Cited by 4
Robust Dynamic Staffing with Predictions
Feng, Y., Manshadi, V., Niazadeh, R., & Neyshabouri, S. (2025) · ACM Conference on Economics and Computation (EC) · doi:10.1145/3736252.3742496 · Cited by 5
A Randomized Caching Algorithm for Distributed Data Access
Zuo, T., Tang, X., & Lee, B. (2024) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infocom52122.2024.10621329 · Cited by 4
Ski Rental Problem with Dynamic Pricing
Bieńkowski, M. (2008) · Cited by 3
Randomized Strategies for Non-additive 3-Slope Ski Rental
Böhnlein, T., Erlich, S., Lotker, Z., & Rawitz, D. (2022) · Lecture notes in computer science · doi:10.1007/978-3-031-09993-9_4 · Cited by 3
Energy-Efficient Design Techniques
Ye, R., & Xu, Q. (2013) · Springer eBooks · doi:10.1007/978-1-4614-4193-9_3 · Cited by 3
Injection Based Dynamic Power Management and a Policy for Multiprocessor Systems
Sun, W. (2013) · International Journal of Networking and Computing · doi:10.15803/ijnc.3.1_137 · Cited by 3
Metrical Service Systems with Multiple Servers
Chiplunkar, A., & Vishwanathan, S. (2014) · Algorithmica · doi:10.1007/s00453-014-9903-7 · Cited by 3
Energy-efficient communication in battery-constrained portable devices
Markopoulou, A. P., Li, Y., Chan, C. W., & Bambos, N. (2005) · International Conference on Broadband Communications, Networks and Systems (BROADNETS) · doi:10.1109/icbn.2005.1589644 · Cited by 3
Model and Methods of Human-Centered Personal Computers Adaptive Power Control
Туркін, І. Б., & Vdovitchenko, O. (2018) · Studies in systems, decision and control · doi:10.1007/978-3-030-00253-4_14 · Cited by 3
A fair and effective scheduling strategy for workstation clusters
Anglano, C. (2002) · IEEE International Conference on Cluster Computing (CLUSTER) · doi:10.1109/clustr.2000.889080 · Cited by 3
Distributed service function chaining in NFV-enabled networks: A game-theoretic learning approach
Alikhani, M., Hakami, V., & Sheikhi, M. (2024) · Journal of Computational Science · doi:10.1016/j.jocs.2024.102399 · Cited by 2
Risk-Sensitive Peak-Aware Energy Scheduling: Competitive and Learning-Augmented Algorithms
Himmelreich, L., Christianson, N., & Wierman, A. (2026) · ACM International Conference on Future Energy Systems (e-Energy) · doi:10.1145/3744255.3811739 · Cited by 3
The Transactional Conflict Problem
Alistarh, D., Haider, S. K., Kübler, R., & Nadiradze, G. (2018) · ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) · doi:10.1145/3210377.3210406 · Cited by 2
An Online Algorithm for Optimizing Network Transmission Cost of Federated Learning in the Cloud
Yan, H., Pan, L., Liu, S., & Wu, D. F. (2025) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2025.3529718 · Cited by 2
Fast Edge Resource Scaling With Distributed DNN
Γιαννακάς, Θ., Tsilimantos, D., Destounis, A., & Spyropoulos, T. (2025) · IEEE Transactions on Network and Service Management · doi:10.1109/tnsm.2025.3532365 · Cited by 2
“In the literature of online algorithms (see, e.g., Ski Rental [21]), a typical practice is to formalize the offline full horizon optimization problem, in order to define the optimal benchmark.”
Optimal Publishing Strategies on a Base Layer
Bar-On, Y., & Mansour, Y. (2025) · Lecture notes in computer science · doi:10.1007/978-3-031-78676-1_18 · Cited by 2
Algorithms for Energy Management
Albers, S. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-13182-0_1 · Cited by 2
A Performance Comparison of Coscheduling Strategies for Workstation Clusters
Anglano, C. (2001) · Cluster Computing · doi:10.1023/a:1011416914729 · Cited by 2
Ordering Policy for Perishable Commodity Using Online Algorithm with Risk-Reward
Liu, B., Cui, W., & Xin, C. (2007) · International Conference on Intelligent Systems and Knowledge Engineering (ISKE) · doi:10.2991/iske.2007.109 · Cited by 2
Competitive Analysis on Financial Leasing Problem
Ma, W., & Wan, S. (2010) · International Conference on Management and Service Science (MASS) · doi:10.1109/icmss.2010.5576278 · Cited by 2
Randomized Competitive Analysis for Two-Server Problems
Bein, W. W., Iwama, K., & Kawahara, J. I. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-87744-8_14 · Cited by 2
Shah, A., & Rajkumar, A. (2021) · Adaptive Agents and Multi-Agents Systems · doi:10.65109/xdvf4075 · Cited by 6
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
“Under competitive analysis, for the two-state problem, an optimal online algo-rithm OWCR is well known for this problem [18, 24, 25]: OWCR switches to ON at a service request.”
BackgroundInfluentialFuzzy 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
Damaschke, P. (1999) · Lecture notes in computer science · doi:10.1007/3-540-46632-0_4 · Cited by 2
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.