Rent, Lease, or Buy: Randomized Algorithms for Multislope Ski Rental
The DOI matches its Crossref record; 18 of the 18 references it cites were found in a registry or an index; none of the 8 sources its claims cite is checked for support yet.
Abstract
In the multislope ski rental problem, the user needs a certain resource for some unknown period of time. To use the resource, the user must subscribe to one of several options, each of which consists of a one-time setup cost (“buying price”) and cost proportional to the duration of the usage (“rental rate”). The larger the price, the smaller the rent. The actual usage time is determined by an adversary, and the goal of an algorithm is to minimize the cost by choosing the best alternative at any point in time. Multislope ski rental is a natural generalization of the classical ski rental problem (where there are only two available alternatives, namely pure rent and pure buy), which is one of the fundamental problems of online computation. The multislope ski rental problem is an abstraction of many problems, where online choices cannot be modeled by just two alternatives, e.g., power management in systems which can be shut down in parts. In this paper we study randomized algorithms for multislope ski rental. Our results include an algorithm that produces the best possible online randomized strategy for any additive instance, where the cost of switching from one alternative to another is the difference in their buying prices, and an e-competitive randomized strategy for any (not necessarily additive) instance.
Overview
CoChat Summary
## TL;DR
The paper studies randomized online algorithms for Multislope Ski Rental and gives an optimal strategy for any additive instance, plus a simple e-competitive strategy for the non-additive case. It also shows a simpler reduction to classical ski rental with competitive ratio \(e/(e-1)\approx 1.582\).
## Key findings
- For additive multislope ski rental, the paper’s main result is an algorithm that computes the best possible randomized online strategy for any given instance.
- The paper proves that if a continuous \(c\)-competitive profile exists, then there exists a prudent \(c\)-competitive profile, and further that any achievable competitive factor can be realized by a tight profile.
- The algorithmic result for the additive case is stated as: an \(O(k \log(1/\varepsilon))\)-time algorithm computes a \((c+\varepsilon)\)-competitive strategy, where \(c\) is the optimal randomized competitive ratio for the instance.
- For the non-additive case, the paper gives a randomized strategy with expected cost at most \(e\) times optimum, improving the best known ratio from \(2/\ln 2 \approx 2.88\) to \(e\).
## Methods
- The paper models a randomized strategy as a profile \(p(t)=(p_0(t),\dots,p_k(t))\), where \(p_i(t)\) is the probability of being in state \(i\) at time \(t\), and analyzes expected rental and buying costs.
- For the additive case, it reduces the search for an optimal strategy to prudent and then tight profiles, derives differential equations governing tight profiles, and uses a feasibility test plus binary search over the competitive ratio.
- For the simpler \(e/(e-1)\)-competitive algorithm, it reduces a \(k{+}1\)-slope instance to \(k\) two-slope ski-rental instances and combines the corresponding strategies.
- For the non-additive case, it uses randomized repeated doubling with \(B_1=\mathrm{opt}(s_1)/(\alpha X)\), \(B_{j+1}=\alpha B_j\), and chooses \(\alpha=e\).
## Limitations
- The paper states that the main additive-case algorithm computes a \((c+\varepsilon)\)-competitive strategy, so the result is approximation-based rather than exact for arbitrary precision \(\varepsilon>0\).
- The text makes evident that the simple \(e/(e-1)\)-competitive construction is a warm-up and only provides an upper bound, not optimality, for the general multislope case; this is an implication from the paper’s framing.
- Not stated in the paper.
Model-written summary. Check it against the paper before relying on it.
Integrity signals
Registry
Cites
Statistics
Figures
Verification
Claims the paper makes
0 Valid · 0 Not valid · 6 Not checked · 27 Own results and interpretations
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
“and an algorithm that produces an e -competitive randomized strategy for any (non-additive) instance.”
- Also stated in: § 1. Introduction · plain
“For the non-additive model, we give a simple e -competitive randomized strategy.”
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 2 assumptions not shown here.
- Also stated in: § 1. Introduction · plain
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
“We now use the results above to construct an algorithm that produces the best possible online strategy for the multislope problem.”
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 3 assumptions 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
“Theorem 5.1. The expected cost of the strategy described above is at most e times the optimum.”
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 3 assumptions 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
“Observation 4.3. Let p 1 and p 2 be two randomized prudent profiles. If B p 1 ( t ) ≥ B p 2 ( t ) for every t , then R p 1 ( t ) ≤ R p 2 ( t ) for every t .”
plainstates an association- 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.
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
“Lemma 3.3. Given ˆ p one can obtain an online strategy whose profile is ˆ p .”
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.
20 more claims
Create a free account to see all 33 claims and every source verdict.
- Probably not a substantial claim. 3
- It may state two separate claims as one. 6
Citations
Cites
Inequalities: Theory of Majorization and Its Applications
Marshall, A. W., Olkin, I., & Arnold, B. C. (2011) · Springer Series in Statistics · doi:10.1007/978-0-387-68276-1 · Cited by 2,567
Karlin, A. R., Manasse, M. S., Rudolph, L., & Sleator, D. D. (1988) · Algorithmica · doi:10.1007/bf01762111 · Cited by 631 · cited 3×
“tegy for any multislope instance by combining strategies for k classical instances. Specifically, what we do is as follows. Let pi be the e e−1-competitive profile for the ith (two slope) instance (see [10]). We define a profile ˆp for the multislope instance as follows: ˆpi(t) = pi 1(t)−pi+1 1 (t) for i ∈{1,...,k−1}, pˆ0…”
BackgroundMethodInfluentialOn-line routing of virtual circuits with applications to load balancing and machine scheduling
Aspnes, J., Azar, Y., Fiat, A., Plotkin, S., & Waarts, O. (1997) · Journal of the ACM · doi:10.1145/258128.258201 · Cited by 330
Competitive randomized algorithms for nonuniform problems
Karlin, A. R., Manasse, M. S., McGeoch, L. A., & Owicki, S. (1994) · Algorithmica · doi:10.1007/bf01189993 · Cited by 258
Motwani, R., Phillips, S., & Torng, E. (1994) · Theoretical Computer Science · doi:10.1016/0304-3975(94)90151-1 · Cited by 232
Online strategies for dynamic power management in systems with multiple power-saving states
Irani, S., Shukla, S., & Gupta, R. (2003) · ACM Transactions on Embedded Computing Systems · doi:10.1145/860176.860180 · Cited by 181
Fleischer, R. (2001) · Theoretical Computer Science · doi:10.1016/s0304-3975(00)00266-8 · Cited by 97
Fleischer, R. (1998) · Lecture notes in computer science · doi:10.1007/3-540-68535-9_10 · Cited by 95
Augustine, J. E., Irani, S., & Swamy, C. (2004) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2004.50 · Cited by 90
Meyerson, A. (2005) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2005.72 · Cited by 81
Research works printed but not linked: 2
- A. Borodin and R. El-Yaniv, Online Computation and Competitive Analysis , Cambridge University Press, Cambridge, UK, 1998.
- S. Gal, Search Games , Academic Press, New York, 1980.
Cited by
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
Multi-Priority Online Scheduling with Cancellations
Wang, X., & Truong, V. (2017) · Operations Research · doi:10.1287/opre.2017.1653 · Cited by 20
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
“Another approach was to define versions of ski rental where the algorithm can choose not necessarily between buying and renting, but possibly between other options, some of which are some mixture between buying and renting [8, 12, 18, 19, 24].”
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 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].”
BackgroundNon-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
Self-citationTo Rent or to Buy in the Presence of Statistical Information: The Constrained Ski-Rental Problem
Khanafer, A., Kodialam, M. S., & Puttaswamy, K. P. N. (2014) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2014.2326988 · Cited by 15
“The solution recovers the competitive ratio, , corresponding to the unconstrained two-slope Ski-Rental problem [8], where we note that .”
BackgroundInfluentialDynamic Balanced Graph Partitioning
Avin, C., Bieńkowski, M., Loukas, A., Pacut, M., & Schmid, S. (2020) · SIAM Journal on Discrete Mathematics · doi:10.1137/17m1158513 · Cited by 26
“, ski rental problem [23, 27], relaxed metrical task systems [8], file migration [8, 10], distributed data management [9, 6, 7], or rent-or-buy network design [5, 34, 19].”
BackgroundOnline Container Scheduling With Fast Function Startup and Low Memory Cost in Edge Computing
Li, Z., Lou, J., Wu, J., Guo, J., Tang, Z., Ping, S., Weijia Jia, B., & Zhao, W. (2024) · IEEE Transactions on Computers · doi:10.1109/tc.2024.3441836 · Cited by 17
“We analogize the container caching for a single container to the complex variant of the ski rental problem [19], [20], [21].”
Online Lower Bounds via Duality
Azar, Y., Cohen, I. R., & Roytman, A. (2017) · ACM-SIAM Symposium on Discrete Algorithms (SODA) · doi:10.1137/1.9781611974782.66 · Cited by 18
“Capital Investment: The online Capital Investment problem (sometimes referred to as the multislope ski rental problem [33]) and its variants have also been studied extensively in the literature.”
BackgroundInfluentialOnline leasing problem with price fluctuations and the second-hand transaction
Feng, X., & Chu, C. (2020) · Journal of Combinatorial Optimization · doi:10.1007/s10878-020-00640-x · Cited by 9
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
“The treatment and notation of multislope ski rental problem in this paper will follow that of [9].”
BackgroundMethodInfluentialFeng, X., Zhang, B., & Dai, Y. (2019) · IEEE Access · doi:10.1109/access.2019.2918693 · Cited by 6
On Generalizations of the Parking Permit Problem and Network Leasing Problems
de Lima, M. S., Felice, M. C. S., & Lee, O. (2017) · Electronic Notes in Discrete Mathematics · doi:10.1016/j.endm.2017.10.039 · Cited by 6
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
“For example, ski-rental problems with non-linear cost functions were studied by (Lotker, Patt-Shamir, and Rawitz 2012; Shi et al. 2018; Fujiwara et al. 2020).”
BackgroundCombinatorial 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
“[32] generalize the original problem to allow multiple options interpolating between renting and buying to be available.”
BackgroundBounds 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
“For a randomized model, refer to, for example, [5], [14]– [16].”
BackgroundOnline Leasing Problem with Price Fluctuations and Second-hand Transaction
Feng, X., Chu, F., Dai, Y., Huang, L., & Chen, N. (2019) · International Conference on Industrial Engineering and Systems Management · doi:10.1109/iesm45758.2019.8948103 · Cited by 4
“[7], [8] and Fujiwara et al.”
Competitive Analysis for Discrete Multiple Online Rental Problems
Hu, M., Xu, W., Li, H., et al. (2018) · Journal of Management Science and Engineering · doi:10.3724/sp.j.1383.303007 · Cited by 4
Dynamic Balanced Graph PartitioningPreprint
Avin, C., Bieńkowski, M., Loukas, A., et al. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1511.02074 · Cited by 4
“, ski rental problem [23, 27], relaxed metrical task systems [8], file migration [8, 10], distributed data management [9, 6, 7], or rent-or-buy network design [5, 34, 19].”
BackgroundA Cost Efficient Online Algorithm for Automotive Idling Reduction
Dong, C., Zeng, H., & Chen, M. (2014) · Proceedings - ACM IEEE Design Automation Conference · doi:10.1145/2593069.2593070 · Cited by 4
Competitive Algorithms for an Online Rent or Buy Problem with Variable Demand
Kodialam, R. (2014) · SIAM Undergraduate Research Online · doi:10.1137/14s013032 · Cited by 4
Competitive Analysis of the Online Leasing Problem for Scarce Resources
Lu, J., Chen, N., & Feng, X. (2023) · International Journal of Environmental Research and Public Health · doi:10.3390/ijerph20010886 · 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
Self-citationPatt-Shamir, B., & Yadai, E. (2020) · ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) · doi:10.1145/3350755.3400280 · Cited by 6
Self-citationA Risk–Reward Model for On-line Financial Leasing Problem with an Interest Rate
Chen, X., & Xu, W. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-59605-1_7 · Cited by 3
A cost efficient online algorithm for automotive idling reduction
Dong, C., Zeng, H., & Chen, M. (2014) · doi:10.1109/dac.2014.6881419 · Cited by 3
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
Fuzzy 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
“Z. Lotker [26] et al. offered to use randomized algorithms for multi slope ski rentals.”
BackgroundCompetitive analysis for two-option online leasing problem under sharing economy
Zhang, Y., Wu, J., Wen-xiong, L., & Hou, M. (2022) · Journal of Combinatorial Optimization · doi:10.1007/s10878-022-00855-0 · Cited by 3
“Meanwhile, they (Lotker et al. 2012) obtained the best possible online randomized strategy for any additive instance, where the cost of switching from one option to another.”
BackgroundCost Minimization Algorithm for Provisioning Cloud Resources
Al‐Enizi, A. M., Ammar, R. A. A., Elfouly, R., et al. (2020) · doi:10.1109/isspit51521.2020.9408841 · Cited by 1
“The authors of [7] studied the Constrained Ski-Rental problem where the assumption is the first moment or the second moment of the arrival distribution is given.”
BackgroundConnected facility leasing problems
de Lima, Felice, M., & Lee, O. (2017) · Cited by 1
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
“Subsequently, they [22] extended the problem to the multislope ski rental problem and computed the best possible randomized online strategy in the additive case.”
Efficient Layer-Granularity Unloading for LLMs in Edge Computing
Li, Z., Tang, Z., Guo, J., Weijia Jia, B., & Zhao, W. (2026) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2026.3697118
Controlling Tail Risk in Two-Slope Ski Rental
Cui, Q., & Dinitz, M. (2025) · Lecture notes in computer science · doi:10.1007/978-3-032-06706-7_6
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
Patt-Shamir, B., & Yadai, E. (2023) · Theory of Computing Systems · doi:10.1007/s00224-023-10126-y
“[6] consider an additive multislope model, and argue that any non-additive ski rental problem can be solved using the generic “repeated doubling” technique, which yields a 4-competitive deterministic algorithm (and an e-competitive randomized algorithm [19]).”
MethodSelf-citationOnline State Exploration: Competitive Worst Case and Learning-Augmented Algorithms
Im, S., Moseley, B., Xu, C., et al. (2023) · Lecture notes in computer science · doi:10.1007/978-3-031-43421-1_20
Efficient index updates for mixed update and query loads
Nepomnyachiy, S., & Suel, T. (2016) · doi:10.1109/bigdata.2016.7840697
“In [26] the authors propose to apply a ski-rental [31] inspired technique to schedule the merging of the inverted file segments.”
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
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
Self-citation
Metadata
- Authors
- Lotker, Z., Patt-Shamir, B., & Rawitz, D.
- Affiliations
- Ben-Gurion University of the Negev (IL)
- Venue
- SIAM Journal on Discrete Mathematics
- Published
- 2012-01
- Volume
- 26
- Issue
- 2
- Pages
- 718-736
- ISSN
- 0895-4801 (ISSN-L)
- 1095-7146
- OpenAlex
- W3023405701
- Semantic Scholar
- 5d664f6c7924e9af66183f0ce6b1ee034c4e51b0
- Cited by
- 39
- References
- 7
- Citations by year
- 2026: 2 · 2025: 3 · 2024: 1 · 2023: 4 · 2022: 2 · 2021: 1 · 2020: 6 · 2019: 3 · 2018: 1 · 2017: 7 · 2016: 1 · 2015: 1 · 2014: 5 · 2013: 2
- FWCI
- 3.36
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- SIAM Journal on Discrete Mathematics (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, randomized algorithms, competitive analysis, online decision making, power management, switching costs
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-01, under version 3 of the claim definition (model deepseek-v4.1-flash, prompt extract-v3).
A second model labelled each claim on 2026-10-01 (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
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.
