The DOI matches its Crossref record; 9 of the 9 references it cites were found in a registry or an index; none of the 1 sources its claims cite is checked for support yet.
Competitive Algorithms for an Online Rent or Buy Problem with Variable Demand
Open accessAbstract
We consider a generalization of the classical Ski Rental Problem motivated by applications in cloud computing.We develop deterministic and probabilistic online algorithms for rent/buy decision problems with time-varying demand.We show that these algorithms have competitive ratios of 2 and 1.582 respectively.We also further establish the optimality of these algorithms.
Overview
CoChat Summary
TL;DR
The paper generalizes the ski-rental problem to online rent-or-buy decisions with time-varying demand, motivated by cloud bursting. It gives a deterministic online algorithm with competitive ratio \(2 - 1/b\) and a randomized algorithm with expected competitive ratio \(e/(e-1)\), and proves both are optimal.
Key findings
- A deterministic online algorithm \(A_{on}\) achieves competitive ratio \(2 - 1/b\), and no deterministic online algorithm can do better.
- A probabilistic online algorithm \(A_{prob}\) achieves expected competitive ratio \(e/(e-1)\), approximately 1.582, and no probabilistic online algorithm can do better.
- In the example with \(b=3\) and demand vector \(\{3,5,2,4,8,1,6\}\), the offline optimum cost is 19, the deterministic online cost is 29 (ratio \(\approx 1.526\)), and the probabilistic expected cost is \(\approx 26.684\) (ratio \(\approx 1.404\)).
- The offline optimum is characterized by buying \(h^n_b\) items initially and renting only when \(d_i > h^n_b\), with cost \(\sum_{i \in S^n_b} d_i + (b-1)h^n_b\).
Methods
- The problem is formalized as an online rent/buy problem where demand \(d_i \ge 0\) arrives once per day, renting costs \(r=1\) per unit per day, and buying costs \(b \ge r\) per unit for all future days.
- The offline problem is solved via a linear program and its dual; the online deterministic algorithm buys up to the \(b\)-th highest demand seen so far, and the probabilistic algorithm randomizes over buying up to the \(a\)-th highest demand for \(a \in \{1,\dots,b\}\).
- Competitive analysis compares online cost to optimal offline cost over all demand vectors; the optimal randomized distribution is derived by equalizing coefficients \(c_a = b p_a + \sum_{j=a+1}^b p_j\), yielding a geometric distribution with ratio \(b/(b-1)\).
Limitations
- The paper states that it is currently studying variants under more general cost models and realistic constraints.
- The paper states that the model abstracts several practical considerations of real-world cloud bursting and that it assumes \(r=1\) and integral \(b\) for convenience, noting results extend by setting \(b\) to \(\lceil b \rceil\).
- Evident from the text: the analysis is worst-case over adversarial demand sequences, assumes demands arrive once per time period, and does not know the number of periods \(n\) in advance.
Model-written summary. Check it against the paper before relying on it.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
0 Valid · 0 Not valid · 2 Not checked · 17 Own results and interpretations
A result the paper states — it cites no source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Theorem 6.2 The probabilistic online algorithm A prob ( D ) achieves an expected competitive ratio ¯ ρ of e e -1 .”
plainstates a cause- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- Rests on an assumption not shown here.
None of the sources cited for this claim have been checked yet.
In the paper
“No deterministic online algorithm operating with the same demands as A on to create a rent/buy schedule to solve the ski-rental problem with demands can have a competitive ratio less than 2 -1 b .”
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- Rests on an assumption not shown here.
A result the paper states — it cites no source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Therefore, it is in the interest of the algorithm designer to make all the coefficients c a equal.”
plainstates a cause- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- Rests on an assumption not shown here.
A result the paper states — it cites no source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“The optimal solution to the dual problem is ∑ i ∈ S n b d i .”
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- Rests on an assumption not shown here.
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“The expected ratio of the probabilistic algorithm's cost to that of the offline algorithm in this example is 26 . 684 19 ≈ 1 . 404.”
plainSingle case- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: unclear — It is unclear whether the paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- Rests on an assumption not shown here.
8 more claims
Create a free account to see all 19 claims and every source verdict.
- Probably not a substantial claim. 5
- It may state two separate claims as one. 1
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
Each contradiction between two passages listed here was confirmed by an independent check.
Rated minor: it would not touch a result — a value no result rests on, a p-value that stays on the same side of the significance level, or a conflict that is clerical, resolved elsewhere in the paper, or outside its own findings.
In the paper
§ 5.1 Online Deterministic Algorithm Example · p. 7
“At all further days t , we will buy ˜ x = h t 3 -h t -1 3 items and rent ˜ y = h t 3 -d t items, as in the table below:”
§ 5 Deterministic Online Algorithm · p. 5
“˜ y k = max { 0 , d k -h k b }”
Rated minor: it would not touch a result — a value no result rests on, a p-value that stays on the same side of the significance level, or a conflict that is clerical, resolved elsewhere in the paper, or outside its own findings.
In the paper
§ Algorithm A prob · p. 11
“Theorem 6.3 No probabilistic online algorithm operating with the same inputs as A prob ( D ) to create a rent/buy schedule to solve the ski-rental problem with demands can have an expected competitive ratio less than e e -1 .”
§ 7 Conclusion and Further Research · p. 12
“A deterministic online algorithm with a competitive ratio of 2 -1 b .”
Citations
Cites
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
Approximation via cost sharing
Gupta, A., Kumar, A., ́al, M. P., et al. (2007) · Journal of the ACM · doi:10.1145/1236457.1236458 · Cited by 84
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
Seagull: intelligent cloud bursting for enterprise applications
Guo, T., Sharma, U. K., Wood, T., et al. (2012) · Cited by 53
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
Rent, Lease or Buy: Randomized Algorithms for Multislope Ski RentalPreprint
Lotker, Z., Patt-Shamir, B., & Rawitz, D. (2008) · arXiv (Cornell University) · Cited by 37
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 15
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 11
Ski Rental Problem with Dynamic Pricing
Bieńkowski, M. (2008) · Cited by 3
Cited by
Improving Online Algorithms via ML Predictions
Kumar, R., Purohit, M., & Svitkina, Z. (2024) · arXiv · doi:10.48550/arxiv.2407.17712 · Cited by 111
“Kodialam [15] considers this generalization and gives a deterministic algorithm with a competitive ratio of 2 as well as a randomized algorithm with competitive ratio of ee − 1 .”
BackgroundOnline Algorithms for Rent-Or-Buy with Expert Advice.
Gollapudi, S., & Panigrahi, D. (2019) · International Conference on Machine Learning · Cited by 169
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
“The ski-rental e−1 problem (Karlin et al., 1994; Lotker et al., 2008; Khanafer et al., 2013; Kodialam, 2014), and variants such as TCP acknowledgment (Karlin et al.”
BackgroundOnline Algorithms for Cost-Effective Cloud Selection with Multiple Demands
Jin, Y., Hayashi, M., & Tagami, A. (2018) · International Teletraffic Congress · doi:10.1109/itc30.2018.00014 · Cited by 4
“One simple extension is the ski-rental problem with multiple demands, which is analyzed in [3].”
Background
Metadata
- Authors
- Kodialam, R.
- Affiliations
- Brooklyn Technical High School (US)
- Corresponding author
- Kodialam, Rohan
- Venue
- SIAM Undergraduate Research Online
- Published
- 2014
- Volume
- 7
- ISSN
- 2327-7807 (ISSN-L)
- OpenAlex
- W2315956051
- Cited by
- 4
- References
- 9
- Citations by year
- 2024: 1 · 2022: 1 · 2019: 1 · 2018: 1
- FWCI
- 0.00
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- SIAM Undergraduate Research Online (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
- ski rental problem, online algorithms, competitive ratio, time-varying demand, cloud computing, randomized algorithms, deterministic algorithms, algorithm optimality
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.
A language model drew the claims from the paper on 2026-10-10, under version 3 of the claim definition (model deepseek-v4.1-flash, prompt extract-v3).
A second model labelled each claim on 2026-10-10 (model jev-1.13-20260917, definition revision gold-guideline-v0.2).
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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Competitive Algorithms for an Online Rent or Buy Problem with Variable Demand. https://app.cochat.ai/papers/10.1137/14s013032
- The paper
- Kodialam, R. (2014). Competitive Algorithms for an Online Rent or Buy Problem with Variable Demand. SIAM Undergraduate Research Online. https://doi.org/10.1137/14s013032
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.