The DOI matches its Crossref record; 8 of the 8 references it cites were found in a registry or an index.
Dynamic TCP Acknowledgment and Other Stories about e/(e - 1)
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
“It has been proved that the best possible competitive ratio for the classical skirental problem against the adaptive adversary approaches to 2.”
From Competitive Analysis for Multi-Commodity Ski-Rental Problem (2022) · cites this paper as Karlin et al., 2003
In the citing paper
“Please note that if we consider all commodities in S as a whole with renting cost d = ∑ s i ∈ S d i and buying cost c = ∑ s i ∈ S c i , the problem can be modeled by the classical ski-rental problem [Karlin et al. , 2003].”
From Competitive Analysis for Multi-Commodity Ski-Rental Problem (2022) · cites this paper as Karlin et al., 2003
In the citing paper
“If we employ the classical ski-rental algorithm on each commodity, the customer will buy all commodities when he/she goes skiing for the hundredth time. Then, the competitive ratio is (9 . 9+10) × 3 10 × 3 = 1 . 99 .”
From Competitive Analysis for Multi-Commodity Ski-Rental Problem (2022) · cites this paper as Karlin et al., 2003
Citations
Cites
Online Computation and Competitive Analysis
Borodin, A., & El‐Yaniv, R. (1998) · Cited by 2,333
Karlin, A. R., Manasse, M. S., Rudolph, L., & Sleator, D. D. (1988) · Algorithmica · doi:10.1007/bf01762111 · Cited by 631 · cited 1×
“There is a natural deterministic online algorithm that achieves a competitive ratio of 2 [ 8 ], and a randomized online algorithm that achieves a competitive ratio of e/(e − 1) (which is about 1.58) in the limit as the ratio between the buy cost and the rent cost becomes large [7].”
BackgroundInfluentialBetter Bounds for Online Scheduling
Albers, S. (1999) · SIAM Journal on Computing · doi:10.1137/s0097539797324874 · Cited by 239
Competitive randomized algorithms for non-uniform problems
Karlin, A. R., Manasse, M. S., McGeoch, L. A., & Owicki, S. S. (1990) · Symposium on Discrete Algorithms · doi:10.5555/320176.320216 · Cited by 158
Fleischer, R. (1998) · Lecture notes in computer science · doi:10.1007/3-540-68535-9_10 · Cited by 95
On-line analysis of the TCP acknowledgment delay problem
Dooly, D. R., Goldman, S. A., & Scott, S. (2001) · Journal of the ACM · doi:10.1145/375827.375843 · Cited by 81
A guessing game and randomized online algorithms
Seiden, S. S. (2000) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/335305.335385 · Cited by 78
TCP Dynamic Acknowledgment Delay: Theory and Practice
Dooly, D. R. (1998) · Open Scholarship Institutional Repository (Washington University in St. Louis) · doi:10.7936/k7db801w · Cited by 24
Cited by
Energy-efficient algorithms for flow time minimization
Albers, S., & Fujiwara, H. (2007) · ACM Transactions on Algorithms · doi:10.1145/1290672.1290686 · Cited by 215
Online Algorithms for Rent-Or-Buy with Expert Advice.
Gollapudi, S., & Panigrahi, D. (2019) · International Conference on Machine Learning · Cited by 169
Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online AlgorithmsPreprint
Wei, A., & Zhang, F. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2010.11443 · Cited by 112
Improving Online Algorithms via ML Predictions
Kumar, R., Purohit, M., & Svitkina, Z. (2024) · arXiv · doi:10.48550/arxiv.2407.17712 · Cited by 111
Optimal Online Multi-Instance Acquisition in IaaS Clouds
Wang, W., Liang, B., & Li, B. (2014) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2014.2385697 · Cited by 101
Augustine, J. E., Irani, S., & Swamy, C. (2004) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2004.50 · Cited by 90
Algorithms for optimizing the bandwidth cost of content delivery
Adler, M., Sitaraman, R. K., & Venkataramani, H. (2011) · Computer Networks · doi:10.1016/j.comnet.2011.07.015 · Cited by 83
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
Online Make-to-Order Joint Replenishment Model: Primal-Dual Competitive Algorithms
Buchbinder, N., Kimbrel, T., Levi, R., Makarychev, K., & Sviridenko, M. (2013) · Operations Research · doi:10.1287/opre.2013.1188 · Cited by 74
Energy-Efficient Algorithms for Flow Time Minimization
Albers, S., & Fujiwara, H. (2006) · Lecture notes in computer science · doi:10.1007/11672142_51 · Cited by 58
Online Resource Procurement and Allocation in a Hybrid Edge-Cloud Computing System
Dinh, T. Q., Liang, B., Quek, T. Q. S., & Shin, H. (2020) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2019.2962795 · Cited by 57
Azar, Y., Ganesh, A., Ge, R., & Panigrahi, D. (2017) · ACM Transactions on Algorithms · doi:10.1145/3055399.3055475 · Cited by 56
General Framework for Metric Optimization Problems with Delay or with Deadlines
Azar, Y., & Touitou, N. (2019) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2019.00013 · Cited by 53
Ski rental with two general options
Lotker, Z., Patt-Shamir, B., & Rawitz, D. (2008) · Information Processing Letters · doi:10.1016/j.ipl.2008.07.009 · Cited by 43
Rent, Lease, or Buy: Randomized Algorithms for Multislope Ski Rental
Lotker, Z., Patt-Shamir, B., & Rawitz, D. (2012) · SIAM Journal on Discrete Mathematics · doi:10.1137/100794018 · Cited by 39
“[9] apply the randomized strategy to TCP acknowledgment batching and other problems.”
MethodBeyond Tree Embeddings – a Deterministic Framework for Network Design with Deadlines or Delay
Azar, Y., & Touitou, N. (2020) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs46700.2020.00129 · Cited by 39
A Primal-Dual Online Deterministic Algorithm for Matching with Delays
Bieńkowski, M., Kraska, A., Liu, H.-H., & Schmidt, P. (2018) · Lecture notes in computer science · doi:10.1007/978-3-030-04693-4_4 · Cited by 37
Rent, Lease or Buy: Randomized Algorithms for Multislope Ski RentalPreprint
Lotker, Z., Patt-Shamir, B., & Rawitz, D. (2008) · arXiv (Cornell University) · Cited by 37
Semi-Online Bipartite MatchingPreprint
Kumar, R., Purohit, M., Schild, A., Svitkina, Z., & Vee, E. (2018) · arXiv (Cornell University) · doi:10.4230/lipics.itcs.2019.50 · Cited by 35
A Match in Time Saves Nine: Deterministic Online Matching with Delays
Bieńkowski, M., Kraska, A., & Schmidt, P. (2018) · Lecture notes in computer science · doi:10.1007/978-3-319-89441-6_11 · Cited by 34
Online Algorithms for Multi-Level AggregationPreprint
Bieńkowski, M., Böhm, M., Byrka, J., Chrobák, M., Dürr, C., Folwarczný, L., Jeż, Ł., Sgall, J., Thắng, N. K., & Veselý, P. (2015) · arXiv (Cornell University) · doi:10.4230/lipics.esa.2016.12 · Cited by 34
Competitive Analysis of Organization Networks or Multicast Acknowledgment: How Much to Wait?
Brito, C. F., Koutsoupias, E., & Vaya, S. (2011) · Algorithmica · doi:10.1007/s00453-011-9567-5 · Cited by 27
Rent, Lease or Buy: Randomized Algorithms for Multislope Ski Rental
Lotker, Z., Patt-Shamir, B., & Rawitz, D. (2008) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.stacs.2008.1331 · Cited by 24
Albers, S. (2006) · Springer eBooks · doi:10.1007/3-540-34874-3_7 · Cited by 23
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
Competitive analysis of organization networks or multicast acknowledgement: how much to wait?
de Brito, C. E. F., Koutsoupias, E., & Vaya, S. (2004) · Symposium on Discrete Algorithms · doi:10.5555/982792.982886 · Cited by 22
Online Algorithms for Multilevel Aggregation
Bieńkowski, M., Böhm, M., Byrka, J., Chrobák, M., Dürr, C., Folwarczný, L., Jeż, Ł., Sgall, J., Thắng, N. K., & Veselý, P. (2020) · Operations Research · doi:10.1287/opre.2019.1847 · Cited by 21
Improved and Deterministic Online Service with Deadlines or Delay
Touitou, N. (2023) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3564246.3585107 · Cited by 21
Online Control Message Aggregation in Chain Networks
Bieńkowski, M., Byrka, J., Chrobák, M., Jeż, Ł., Sgall, J., & Stachowiak, G. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-40104-6_12 · Cited by 20
The Online Set Aggregation Problem
Carrasco, R. A., Pruhs, K. R., Stein, C., & Verschae, J. (2018) · Lecture notes in computer science · doi:10.1007/978-3-319-77404-6_19 · Cited by 20
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
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
Gupta, A., Kumar, A., & Panigrahi, D. (2020) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3357713.3384277 · Cited by 19
Smart air-conditioning control by wireless sensors: an online optimization approach
Aftab, M., Chau, C.-K., & Armstrong, P. R. (2013) · ACM International Conference on Future Energy Systems (e-Energy) · doi:10.1145/2487166.2487192 · Cited by 19
New results on multi-level aggregation
Bieńkowski, M., Böhm, M., Byrka, J., Chrobák, M., Dürr, C., Folwarczný, L., Jeż, Ł., Sgall, J., Thắng, N. K., & Veselý, P. (2021) · Theoretical Computer Science · doi:10.1016/j.tcs.2021.02.016 · Cited by 18
Rent 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
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
Controlling Tail Risk in Online Ski-Rental
Dinitz, M., Im, S., Lavastida, T., Moseley, B., & Vassilvitskii, S. (2024) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611977912.147 · Cited by 16
On Energy Conservation in Data Centers
Albers, S. (2019) · ACM Transactions on Parallel Computing · doi:10.1145/3364210 · Cited by 15
O(depth)-competitive algorithm for online multi-level aggregationPreprint
Buchbinder, N., Feldman, M., Naor, J. S., & Talmon, O. (2017) · arXiv (Cornell University) · doi:10.5555/3039686.3039766 · Cited by 15
Caching with Time Windows and Delays
Gupta, A., Kumar, A., & Panigrahi, D. (2022) · SIAM Journal on Computing · doi:10.1137/20m1346286 · Cited by 14
Nearly-Tight Lower Bounds for Set Cover and Network Design with Deadlines/Delay
Touitou, N. (2021) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.isaac.2021.53 · Cited by 14
Saha, G., & Pasumarthy, R. (2015) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2015.7447117 · Cited by 14
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
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
Online bin packing with delay and holding costs
Ahlroth, L., Schumacher, A., & Orponen, P. (2012) · Operations Research Letters · doi:10.1016/j.orl.2012.10.006 · Cited by 11
On Time Lookahead Algorithms for the Online Data Acknowledgement Problem
Imreh, C., & Németh, T. (2007) · Lecture notes in computer science · doi:10.1007/978-3-540-74456-6_27 · Cited by 10
Online Facility Location with Linear DelayPreprint
Bieńkowski, M., Böhm, M., Byrka, J., & Marcinkowski, J. (2021) · arXiv (Cornell University) · doi:10.4230/lipics.approx/random.2022.45 · Cited by 10
Nearly-Optimal Algorithm for Non-Clairvoyant Service with Delay
Touitou, N. (2025) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.stacs.2025.74 · Cited by 9
Frameworks for Nonclairvoyant Network Design with Deadlines or Delay
Touitou, N. (2023) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.icalp.2023.105 · Cited by 9
Competitive Analysis for Two-Level Ski-Rental Problem
Wu, B., Bao, W., & Yuan, D. (2021) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v35i13.17429 · Cited by 9
Parameter learning algorithm for the online data acknowledgment problem
Imreh, C., & Németh, T. (2011) · Optimization methods & software · doi:10.1080/10556788.2010.544313 · Cited by 8
Randomized online edge service renting: Extending cloud-based CDN to edge environments
Jin, Z., Pan, L., & Liu, S. (2022) · Knowledge-Based Systems · doi:10.1016/j.knosys.2022.109957 · Cited by 8
Algorithms for Optimizing Bandwidth Costs on the Internet
Adler, M., Sitaraman, R. K., & Venkataramani, H. (2006) · IEEE Workshop on Hot Topics in Web Systems and Technologies (HotWeb) · doi:10.1109/hotweb.2006.355262 · Cited by 8
Online Function Tracking with Generalized Penalties
Bieńkowski, M., & Schmid, S. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-13731-0_34 · Cited by 8
Replenishment policy for a purchase-to-order seller: a tradeoff between ordering cost and delay cost
Ni, G. (2019) · International Journal of Production Research · doi:10.1080/00207543.2019.1616846 · Cited by 8
Online TCP Acknowledgment Under General DelaysPreprint
Bhore, S., Pawŀowski, M., & Umboh, S. W. (2026) · arXiv (Cornell University) · doi:10.4230/lipics.approx/random.2026.26 · Cited by 7
Patt-Shamir, B., & Yadai, E. (2020) · ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) · doi:10.1145/3350755.3400280 · Cited by 6
The 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
Chrobák, M. (2014) · ACM SIGACT News · doi:10.1145/2596583.2596603 · Cited by 6
Competitive Analysis for Multi-Commodity Ski-Rental Problem
Wu, B., Bao, W., Yuan, D., & Zhou, B. (2022) · Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence · doi:10.24963/ijcai.2022/648 · 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
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
Advanced Techniques for Dynamic Programming
Bein, W. W. (2013) · Springer eBooks · doi:10.1007/978-1-4419-7997-1_28 · Cited by 5
On the remote server problem or more about TCP acknowledgments
Epstein, L., & Kesselman, A. (2006) · Theoretical Computer Science · doi:10.1016/j.tcs.2006.09.003 · Cited by 5
Online gathering algorithms for wireless networks
Korteweg, P. (2008) · Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands · doi:10.6100/ir633780 · Cited by 5
Competitive 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 Capacity Scaling Augmented With Unreliable Machine Learning PredictionsPreprint
Rutten, D., & Mukherjee, D. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2101.12160 · Cited by 4
Robust and Consistent Ski Rental with Distributional AdvicePreprint
Kim, J., & Fan, C. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2603.29233 · Cited by 4
Ski Rental Problem with Dynamic Pricing
Bieńkowski, M. (2008) · Cited by 3
Parameter learning in lookahead online algorithms for data acknowledgment
Németh, T., Gyekiczki, B., & Imreh, C. (2011) · IEEE International Symposium on Logistics and Industrial Informatics (LINDI) · doi:10.1109/lindi.2011.6031146 · Cited by 3
Competitive Data-Structure Dynamization
Mathieu, C., Rajaraman, R., Young, N. E., & Yousefi, A. (2021) · ACM Transactions on Algorithms · doi:10.1145/3672614 · Cited by 3
Competitive analysis of online leasing problem with discount quotation
Liu, B., Xin, C., & Kan, S. (2011) · International Conference on Advanced Computational Intelligence (ICACI) · doi:10.1109/iwaci.2011.6160084 · Cited by 3
Dynamic TCP acknowledgment with sliding window
Koga, H. (2008) · Theoretical Computer Science · doi:10.1016/j.tcs.2008.12.017 · Cited by 3
Online algorithms in resource management and constraint satisfaction
Ahlroth, L. (2012) · Aaltodoc (Aalto University) · Cited by 3
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
An online cost optimization approach for edge resource provisioning in cloud gaming
Tian, G., Pan, L., & Liu, S. (2024) · Journal of Network and Computer Applications · doi:10.1016/j.jnca.2024.104008 · Cited by 2
Approximation for Batching via Priorities
Bein, W. W., Noga, J., & Wiegley, J. (2007) · Scientific Annals of Computer Science · doi:10.5281/zenodo.12705158 · Cited by 2
Online Covering with Maximum Delay under Subadditive Service CostsPreprint
Lu, T., Ren, R., & Liu, S. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2609.32675 · Cited by 2
Simultaneous Competitive and Regret Guarantees for TCP AcknowledgmentPreprint
Harada, T., Kawase, Y., & Sumita, H. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2610.13571 · Cited by 2
Priority Approximation for Batching
Bein, W. W., Noga, J., & Wiegley, J. (2008) · doi:10.1109/hicss.2008.508 · Cited by 1
Competitive Analysis of Two Special Bahncard Replacement Problem
Ding, L., Liu, X., & Kang, W. (2009) · Journal of Applied Sciences · doi:10.3923/jas.2009.1185.1189 · Cited by 1
$O(\mbox{depth})$-Competitive Algorithm for Online Multi-level AggregationPreprint
Buchbinder, N., Feldman, M., Naor, J. S., & Talmon, O. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1701.01936 · Cited by 1
Online Bin Packing with Per-Bin Maximum DelayPreprint
Lu, T., Ren, R., & Liu, S. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2609.29589 · Cited by 1
Pure Tail Constraints for Online ProblemsPreprint
Basiak, M., Bieńkowski, M., Shin, Y., & Tatarczuk, A. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2609.35337 · Cited by 1
Online Batching with Lookahead: Adversarial Limits and Stochastic GainsPreprint
Christou, D., Chen, J., Sharma, N., Akella, A., Chawla, S., & Shakkottai, S. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2610.16013 · Cited by 1
On-line előrenéző és paraméter tanuló algoritmusok nyugtázási és ütemezési problémákra
Németh, T. (2014) · SZTE Repository of Dissertations (University of Szeged) · doi:10.14232/phd.1894
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
Dynamic TCP Acknowledgment with Sliding Window
Koga, H. (2007) · Lecture notes in computer science · doi:10.1007/978-3-540-73951-7_56
Non-Additive Two-Option Ski Rental
Levi, A., & Patt-Shamir, B. (2013) · Lecture notes in computer science · doi:10.1007/978-3-319-03578-9_7
Approximation in batch and multiprocessor scheduling.
Nonner, T. (2010) · FreiDok plus (Universitätsbibliothek Freiburg)
Approximation Algorithms for Covering Problems
Koufogiannakis, C. (2009) · eScholarship (California Digital Library)
Online Hedge Reservation for Diverse Plans and Competitive Analysis
Wu, B., Bao, W., Yuan, D., & Zhou, B. B. (2021) · Proceedings of the International Conference on Automated Planning and Scheduling · doi:10.1609/icaps.v31i1.15985
Patt-Shamir, B., & Yadai, E. (2023) · Theory of Computing Systems · doi:10.1007/s00224-023-10126-y
Improved and Parameterized Algorithms for Online Multi-Level AggregationPreprint
Lin, Y., & Turoczy, A. (2025) · arXiv (Cornell University) · doi:10.4230/lipics.swat.2026.31
LIPIcs, Volume 1, STACS'08, Complete Volume
Albers, S., & Weil, P. (2013) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.stacs.2008
A Tight Lower Bound for Online Service with Deadlines and Lazy Server
Disser, Y., & Thelen, L. (2025) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.isaac.2025.26
Algorithms Under Uncertainty : Robust Methods and Decision-Theoretic Evaluation
Melidi, G. (2025) · theses.fr (ABES) · doi:10.70675/679db8e1z0498z4941zacf6z3cbcb818019a
A Sharp Additive Bound for the Threshold Rule in Repeated Rent-or-BuyPreprint
Schiavo, V. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2611.06955
Metadata
- Authors
- Karlin, Kenyon, & Randall
- Affiliations
- École Polytechnique (FR)
- Georgia Institute of Technology (US)
- Venue
- Algorithmica
- Published
- 2003-07
- Volume
- 36
- Issue
- 3
- Pages
- 209-224
- ISSN
- 0178-4617 (ISSN-L)
- 1432-0541
- OpenAlex
- W2031816824
- Cited by
- 73
- References
- 8
- Citations by year
- 2024: 2 · 2023: 2 · 2022: 5 · 2021: 5 · 2020: 6 · 2019: 4 · 2018: 3 · 2017: 4 · 2015: 3 · 2014: 3 · 2013: 6 · 2012: 2
- FWCI
- 2.62
- 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
- Social Sciences › Decision Sciences › Management Science and Operations Research › Advanced Bandit Algorithms Research
- Keywords
- ski rental problem, randomized online algorithms, competitive ratio, optimal online algorithms, online decision making
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.