Ski Rental and Rent-or-Buy — Senior Level¶

Prerequisites¶

• Middle Level — the break-even deterministic algorithm (2 − 1/B optimal), the randomized e/(e−1) algorithm with its buy-day schedule, and the Bahncard variant stated
• Competitive Analysis — Senior — adversary hierarchy, the potential method, and Yao's principle as von Neumann minimax / LP duality, which we invoke throughout
• Paging and Caching Theory — Senior — the H_k randomized paging bound, another Yao-certified online lower bound

Table of Contents¶

1. What Senior-Level Ski Rental Is About
2. The e/(e−1) Randomized Lower Bound via Yao
3. Ski Rental as a Covering LP: The Primal–Dual View
4. The Online Primal–Dual Framework (Buchbinder–Naor)
5. Worked Derivation: Randomized Ski Rental by Primal–Dual
6. The Rent-or-Buy Family
7. Leasing and the Parking-Permit Problem
8. Learning-Augmented Ski Rental (Purohit–Svitkina–Kumar)
9. Decision Framework
10. Research Pointers
11. Key Takeaways

What Senior-Level Ski Rental Is About¶

Junior and middle levels teach ski rental as a single, self-contained puzzle with two clean answers. You rent skis for 1 per day or buy them once for B; you do not know the season length D. The deterministic optimum rents for B − 1 days, then buys, achieving competitive ratio 2 − 1/B, and no deterministic algorithm does better. Randomizing the buy day — buying on day t with probability proportional to (1 − 1/B)^{B−t} — improves the ratio to e/(e−1) ≈ 1.582, and the Bahncard problem generalizes the same idea to a discount card with an expiry window.

Senior-level ski rental is about why this single problem sits at the conceptual center of online algorithms, and the three threads that radiate from it:

1. Ski rental is the canonical "irrevocable one-time investment under uncertainty" problem. Its e/(e−1) constant is not folklore — it is the exact game value, provably optimal by Yao's principle. Knowing how to construct the hard distribution that certifies optimality is the senior skill; reciting the constant is the junior one.
2. Ski rental is the seed of the online primal–dual method. Buchbinder and Naor showed that both the deterministic 2 and the randomized e/(e−1) algorithms fall out mechanically from a covering LP and its packing dual, by raising primal and dual variables in lockstep. This is the unifying modern lens: once you see ski rental as an LP, the same machinery derives set cover, caching, ad-allocation, and network design.
3. Ski rental is the prototype of a whole family. TCP acknowledgment, the Bahncard, multi-shop rental, Steiner / single-source rent-or-buy network design, Meyerson's parking-permit (multi-option leasing), and — most consequentially — learning-augmented algorithms, the field PSK launched in 2018 by giving ski rental a prediction and trading consistency against robustness.

The through-line: every problem in which you repeatedly pay a small recurring cost until you make a single large irrevocable commitment is "ski rental wearing a costume." Recognizing the costume — and knowing which generalization (random buy day, fractional primal–dual, learned threshold) the situation licenses — is what this level is for.

The e/(e−1) Randomized Lower Bound via Yao¶

Middle level exhibits a randomized algorithm achieving e/(e−1). Senior level proves that no randomized algorithm can do better against an oblivious adversary — the algorithm is optimal, not merely good. The tool is Yao's principle: invent a distribution over inputs on which every deterministic algorithm is bad in expectation, and you have lower-bounded every randomized algorithm.

The setup and the deterministic strategy space¶

Normalize so renting costs 1/day and buying costs B (an integer, with B → ∞ taken at the end to extract the clean constant). A deterministic ski-rental algorithm is fully described by a single number: the day j ∈ {0, 1, 2, …} on which it buys (j = 0 means "buy immediately"; j = ∞ means "never buy"). If the season lasts D days, the algorithm's cost is

   ALG_j(D) = j + B      if D > j     (rented j days, then bought)
   ALG_j(D) = D          if D ≤ j      (rented the whole season, never bought)

while the offline optimum is OPT(D) = min(D, B).

Constructing the hard distribution¶

We place a distribution q on the season length D and compute, for each deterministic buy-day j, the expected ratio E_{D∼q}[ALG_j(D)] / E_{D∼q}[OPT(D)]. Yao's principle says the best deterministic algorithm's expected ratio under the worst q lower-bounds every randomized algorithm. So the adversary's job is to choose q making every j simultaneously bad.

The right q is geometric over the season length, supported on D ∈ {1, 2, …, B} (seasons longer than B only help the algorithm — OPT caps at B and the algorithm should certainly have bought — so the adversary concentrates mass on D ≤ B). Put

   Pr[D ≥ i] ∝ (1 − 1/B)^{i}      i.e. the survival function decays geometrically.

Concretely let Pr[D = i] = c · (1 − 1/B)^{i−1} · (1/B) for i = 1, …, B−1, with the residual probability mass placed at D = B (so the distribution is properly normalized over {1, …, B}). The decay rate (1 − 1/B) is chosen precisely so that the marginal gain of postponing the buy day by one — saving a possible buy if the season ends now, versus paying one more rental day if it does not — is balanced for every j.

Why every deterministic algorithm has ratio ≥ e/(e−1)¶

Compute the adversary-relative cost of buying on day j. The key identity: under the geometric q, the expected cost E[ALG_j(D)] is constant in j — the distribution is engineered so the player is indifferent between all buy days. Intuitively:

• Postponing the buy from day j to j+1 saves B whenever the season happens to end exactly on day j+1 (you avoided buying), an event of probability ≈ (1/B)·(1−1/B)^{j}, saving B · (1/B)(1−1/B)^j = (1−1/B)^j.
• Postponing costs one extra rental day 1 whenever the season outlasts day j+1, an event of probability Pr[D > j+1] ≈ (1−1/B)^{j+1}.

Setting these equal — (1−1/B)^j = 1 · (1−1/B)^{j+1} up to the normalizing constant — is exactly what the geometric decay enforces, so every j yields the same expected algorithm cost. The expected optimum is

   E[OPT(D)] = E[min(D, B)] = Σ_{i≥1} Pr[D ≥ i] · (cost of surviving day i).

Carrying out the two sums and taking B → ∞, the ratio of E[ALG_j] to E[OPT] converges to

$$\frac{\mathbb{E}[\text{ALG}_j]}{\mathbb{E}[\text{OPT}]} \;\longrightarrow\; \frac{1}{1 - (1 - 1/B)^{B}} \;\xrightarrow[B\to\infty]{}\; \frac{1}{1 - e^{-1}} \;=\; \frac{e}{e - 1} \approx 1.582,$$

using the defining limit (1 − 1/B)^B → 1/e. Because every deterministic j achieves exactly this ratio under q, the best deterministic algorithm against q has ratio e/(e−1). By Yao:

Theorem (randomized ski-rental lower bound). No randomized algorithm for ski rental is better than e/(e−1)-competitive against an oblivious adversary.

Combined with the matching algorithm from middle.md, this proves the randomized algorithm is optimal: e/(e−1) is the value of the ski-rental game. The same (1 − 1/B)^B → 1/e mechanism that builds the algorithm's buy-day schedule also builds the adversary's hard distribution — algorithm and lower bound are two faces of the same geometric balance. This is the identical pattern by which randomized paging's H_k bound is certified (paging senior); ski rental is its single-threshold cousin.

Ski Rental as a Covering LP: The Primal–Dual View¶

The modern, unifying way to derive (not just verify) ski-rental algorithms is to write the problem as a linear program and apply the online primal–dual schema. This reframing is due to Buchbinder and Naor, and it is the lens that makes ski rental a textbook special case of online covering.

The fractional formulation¶

Let x ∈ [0, 1] be the "fraction of the buy decision committed" — think of it as the probability that the (randomized) algorithm has already bought, or equivalently a fractional purchase that we later round/interpret. Let z_i ≥ 0 be the fractional amount we are still renting on day i. On every day i that the season survives, the algorithm must "cover" that day: either it has bought (x) or it is renting (z_i). The covering constraint per day is x + z_i ≥ 1. Renting day i costs z_i; buying costs B·x. With a season of (unknown, online-revealed) length, the LP for a T-day season is:

   PRIMAL (covering):
     minimize    B·x  +  Σ_{i=1}^{T} z_i
     subject to  x + z_i ≥ 1        for each day i = 1, …, T
                 x ≥ 0,  z_i ≥ 0

The constraints arrive online: day i's constraint x + z_i ≥ 1 appears only when the season reaches day i. The algorithm must keep x and the z_i feasible at all times and may only increase variables (monotone, irrevocable — you cannot un-buy).

The packing dual¶

The LP dual assigns a variable y_i ≥ 0 to each day-i constraint:

   DUAL (packing):
     maximize    Σ_{i=1}^{T} y_i
     subject to  Σ_{i=1}^{T} y_i ≤ B        (the column for x: total dual on buy ≤ B)
                 y_i ≤ 1                     (the column for z_i: dual per rent-day ≤ 1)
                 y_i ≥ 0

The dual reads beautifully: y_i is the "value extracted" from covering day i; renting caps each day's value at 1 (the rent cost), and buying caps the total extracted value at B (the buy cost). Weak duality — any feasible dual is a lower bound on any feasible primal, hence on OPT — is what turns dual feasibility into a competitive guarantee: if we maintain PRIMAL_cost ≤ c · DUAL_value while keeping the dual feasible, then PRIMAL_cost ≤ c · OPT. The entire algorithm-design task becomes: raise primal and dual together so the primal cost never exceeds c times the growing dual.

This is the same covering/packing duality that underlies online set cover and caching — ski rental is the one-constraint-column, one-buy-column minimal instance, which is exactly why it is the pedagogical entry point to the whole framework.

The Online Primal–Dual Framework (Buchbinder–Naor)¶

Buchbinder and Naor's "The Design of Competitive Online Algorithms via a Primal–Dual Approach" (2009) abstracts a recipe that derives competitive online algorithms for the entire class of online covering/packing LPs. The schema:

1. Formulate the online problem as a covering LP (constraints arrive over time) with its packing dual.
2. On each arriving constraint, if it is already satisfied, do nothing. If it is violated, raise the relevant primal variables continuously (a differential update), and simultaneously raise the corresponding dual variable y_i, until the primal constraint becomes tight (satisfied).
3. Couple the rates so that d(PRIMAL_cost) ≤ c · d(DUAL_value) at every instant. Then integrating over the run gives PRIMAL ≤ c · DUAL ≤ c · OPT by weak duality.

The art is the update rule — the differential equation governing how fast a primal variable grows as a function of its current value. For covering LPs the canonical rule is multiplicative-with-additive-boost:

$$\frac{dx}{dy_i} \;=\; \frac{1}{\text{cost}(x)}\Bigl(x + \frac{1}{\,\text{(number of variables in the constraint)}\,}\Bigr),$$

which produces the characteristic exponential growth x ≈ (e^{(\text{coverage})} − 1)/(e − 1) that yields the e/(e−1)-style constants. The two ski-rental algorithms correspond to two ways of reading this same primal variable:

• Read x as a deterministic threshold (buy once x crosses 1): yields the 2-competitive deterministic algorithm.
• Read x as a probability / fractional purchase (buy on a randomized day whose CDF is x): yields the e/(e−1)-competitive randomized algorithm.

One LP, one update rule, two competitive results — this is why the primal–dual view unifies what middle level presented as two unrelated tricks.

Worked Derivation: Randomized Ski Rental by Primal–Dual¶

We now derive the e/(e−1) randomized algorithm end-to-end from the LP, making the framework concrete.

The continuous update¶

Process the season day by day. When day i arrives, its constraint x + z_i ≥ 1 is new and (since z_i starts at 0) violated unless x ≥ 1 already. To satisfy it cheaply we set z_i = 1 − x (rent the uncovered fraction) — but before doing so, we raise x a little, paying for the increase by raising the dual y_i. The coupled differential update, with B the buy cost, is:

$$\boxed{\;\frac{dx}{dt} \;=\; \frac{1}{B}\,\Bigl(x + \frac{1}{B-1}\Bigr), \qquad \frac{dy_i}{dt} = 1\;}$$

where t indexes "rental pressure" accumulated on day i. Integrating the linear ODE x' = (x + \tfrac{1}{B-1})/B from x(0) = 0 over one day's worth of pressure gives the closed form after i days:

$$x(i) \;=\; \frac{1}{B-1}\left[\Bigl(1 + \tfrac{1}{B}\Bigr)^{i} - 1\right] \;\approx\; \frac{e^{\,i/B} - 1}{e - 1}\quad(\text{as } B \to \infty,\ i = \Theta(B)).$$

So x grows exponentially in the number of days survived, reaching 1 at i ≈ B — the algorithm has "fully bought" right around the break-even point, but it has been accumulating purchase probability along the way.

Reading x as a buy-day distribution¶

Interpret x(i) as the cumulative probability that the algorithm has bought by day i. The probability of buying exactly on day i is the increment x(i) − x(i−1), which from the ODE is proportional to (1 + 1/B)^{i} ≈ e^{i/B} — equivalently, reading days from the end, proportional to (1 − 1/B)^{B − i}, exactly the truncated-geometric buy-day schedule from middle.md. The primal–dual derivation has re-discovered the optimal randomized algorithm mechanically, with no clever guessing.

The competitive ratio falls out of the coupling¶

The primal cost increment when we raise x by dx and set the rent is B·dx + z_i; the dual increment is dy_i. The update rule's coefficients were chosen precisely so that

   d(PRIMAL) ≤ (e/(e−1)) · d(DUAL)   at every instant,

because the additive boost 1/(B−1) makes the multiplicative growth's "tax" integrate to the factor 1/(1 − 1/e) = e/(e−1). Integrating over the whole run and applying weak duality DUAL ≤ OPT:

$$\text{ALG} \;=\; \text{PRIMAL} \;\le\; \frac{e}{e-1}\cdot \text{DUAL} \;\le\; \frac{e}{e-1}\cdot \text{OPT}.$$

The deterministic 2-competitive algorithm comes from the same ODE with the additive boost set to 1 and x thresholded rather than randomized — the boost coefficient is the single dial that tunes the constant from 2 down to e/(e−1). This is the senior payoff: the framework, not a trick, produces both algorithms, and the lower bound of the previous section certifies the randomized one is the framework's best possible output.

The Rent-or-Buy Family¶

Ski rental is the atom; the molecules are the rent-or-buy problems — any setting trading recurring "rent" costs against a one-time "buy." Each member inherits ski rental's 2-deterministic / e/(e−1)-randomized signature, sometimes exactly, sometimes with a twist.

TCP acknowledgment / dynamic TCP¶

In the TCP acknowledgment problem (Dooly, Goldman, Scott 1998; the dynamic/online version analyzed by Karlin, Kenyon, and Randall 2001), a stream of data packets arrives and the receiver must send acknowledgments. Each ACK costs 1 (a fixed overhead) but may acknowledge several packets at once; delaying an ACK accrues a per-packet latency cost. The decision "ack now, or wait and risk more latency to batch more packets" is structurally rent-or-buy in time: waiting "rents" latency, sending "buys" an acknowledgment.

Theorem (Karlin–Kenyon–Randall 2001). The optimal randomized online algorithm for single-acknowledgment TCP is e/(e−1)-competitive against an oblivious adversary, and this is tight; the optimal deterministic algorithm is 2-competitive.

The e/(e−1) is exactly ski rental's constant — and the proof uses the same Yao-style geometric hard distribution, now over packet-arrival patterns. KKR's contribution was identifying the right potential/LP and proving the matching lower bound, cementing TCP-ack as ski rental's canonical "in the wild" appearance.

The Bahncard problem (Fleischer)¶

Fleischer (2001) introduced the Bahncard problem, generalizing ski rental to a discount card with an expiry window. A traveler pays full price p per trip, or buys a "Bahncard" for cost C that gives a discount factor β ∈ (0,1) on every trip for a limited validity period T. Unlike ski rental, the buy is not permanent — the card expires, so the decision recurs, and the algorithm faces a sequence of overlapping ski-rental-like decisions over a sliding time window.

Theorem (Fleischer 2001). There is a 2-competitive deterministic algorithm for the Bahncard problem, and the optimal randomized algorithm is e/(e − 1 + β)-competitive (which degrades gracefully to ski rental's e/(e−1) as β → 0, i.e. when the card is "free per trip" after purchase).

The Bahncard is the bridge from one-shot ski rental to recurring rent-or-buy: the expiry window is what couples consecutive decisions, and Fleischer's analysis shows the per-window structure still reduces to a ski-rental core. (See middle.md for the problem statement; the senior content is the e/(e−1+β) randomized bound and its window-coupling proof idea.)

Multi-shop ski rental and network rent-or-buy¶

Multi-shop ski rental offers several shops, each with its own rent and buy prices; the algorithm must choose where as well as when to buy. The extra dimension does not break the framework — the primal–dual LP simply gains a buy-column per shop — and the competitive ratios remain in the ski-rental family.

The deepest generalization is network design rent-or-buy, where ski rental's "buy once to stop paying" logic governs edges of a graph:

• Single-source rent-or-buy (SROB): connect a set of demand nodes to a single source; each edge can be rented per unit of flow routed through it, or bought for a fixed cost after which flow is free. The tension is identical to ski rental, replicated across every edge, with the twist that aggregating flow makes buying worthwhile. Constant-competitive randomized algorithms (and constant-factor approximations in the offline/stochastic setting) are obtained via ski-rental-style per-edge decisions: each edge independently runs a randomized buy-or-rent rule, and the e/(e−1) instinct aggregates to a constant overall.
• Steiner rent-or-buy and buy-at-bulk: the same rent-vs-buy tension with Steiner connectivity (multiple sources/sinks) and economies of scale on edge capacities. Sample-and-augment and primal–dual algorithms achieve small constant approximation ratios; the online versions lean directly on the ski-rental primitive at each edge.

The unifying claim: wherever a system must decide between paying-as-you-go and a capacity-buying commitment, the local decision is a ski-rental instance, and the global competitive ratio is built by composing these local e/(e−1)-style decisions — which is exactly why mastering the one-variable LP above pays off across network design.

Leasing and the Parking-Permit Problem¶

Ski rental has a binary menu: rent (per day) or buy (forever). The natural generalization is a menu of leases of different durations and prices — and this is Meyerson's parking-permit problem (Meyerson 2005), the "multi-option ski rental."

The model¶

You must hold a valid parking permit on every day you drive (the days you drive are revealed online, adversarially). The menu offers K permit types: type k costs c_k and is valid for a duration d_k. Economies of scale make longer permits cheaper per day (c_k / d_k decreasing in k), so the decision generalizes ski rental's two options to K: on each driving day, which permit(s) to buy to cover present and anticipated future driving, hedging against an unknown future.

Ski rental is exactly the K = 2 case: a "1-day permit" (rent) and an "infinite permit" (buy).

Theorem (Meyerson 2005). The parking-permit problem admits an O(K)-competitive deterministic algorithm and an O(log K)-competitive randomized algorithm, and these bounds are tight (there are matching Ω(K) deterministic and Ω(log K) randomized lower bounds).

Why the bounds take this shape¶

The log K gap between deterministic and randomized mirrors ski rental's 2-vs-e/(e−1) gap, scaled by the number of options. The randomized algorithm runs an interval / multi-level version of the geometric buy-day schedule: at each permit level it makes a ski-rental-style randomized commitment, and the log K levels compose to the O(log K) ratio. The deterministic O(K) comes from a level-by-level threshold rule. Parking permit is the load-bearing leasing primitive: it underlies online leasing versions of facility location, Steiner tree, and set cover (Anthony–Gupta and others), where infrastructure is "leased" for varying durations rather than bought once — and in every case the local decision is a parking-permit (hence multi-option ski-rental) instance.

The lesson: when your "buy" is not permanent but comes in several durations, you are in parking-permit territory, and the achievable ratio degrades from ski rental's constants to O(K) / O(log K) in the number of lease options.

Learning-Augmented Ski Rental (Purohit–Svitkina–Kumar)¶

The most consequential modern descendant of ski rental is the learning-augmented (a.k.a. algorithms with predictions) model. Mahdian, Nazerzadeh, and Saberi (2012) had earlier studied online algorithms aided by an optimistic alternative, but Purohit, Svitkina, and Kumar (NeurIPS 2018) crystallized the framework using ski rental as the seminal example — and it launched an entire subfield.

The model: prediction + robustness parameter¶

The algorithm receives a prediction y of the true season length D (from some ML model — possibly accurate, possibly garbage). Define the prediction error η = |y − D|. The algorithm also has a trust parameter λ ∈ (0, 1] set by the engineer: small λ means "trust the prediction," large λ means "hedge against it being wrong." We want two guarantees simultaneously:

• Consistency: if the prediction is perfect (η = 0), the competitive ratio approaches 1 — the algorithm exploits a good prediction.
• Robustness: no matter how wrong the prediction is, the competitive ratio stays bounded by a constant — the algorithm never does worse than a fixed multiple of OPT.

A pure online algorithm ignores y and gets e/(e−1) always; a "follow the prediction blindly" algorithm gets ratio 1 when y is right but unbounded ratio when y is wrong. The art is interpolating between them with the single dial λ.

The deterministic learning-augmented algorithm¶

PSK's deterministic rule. Given prediction y and buy cost B = 1 (normalized so buying costs 1, renting 1/B'… we keep B as the buy cost for clarity):

   if y ≥ B:   (prediction says "long season, you'll want to buy")
       buy on day  ⌈λ·B⌉           — buy early, trusting the prediction
   else:       (prediction says "short season, just rent")
       buy on day  ⌈B/λ⌉           — buy late, hedging against the prediction

The single parameter λ shifts the buy day earlier (aggressive, prediction-trusting) or later (conservative, prediction-hedging).

Theorem (Purohit–Svitkina–Kumar 2018, deterministic). This algorithm is (1 + λ)-consistent and (1 + 1/λ)-robust: its competitive ratio is at most $$\min!\left(\,\frac{1 + \lambda}{1}\,,\ \ 1 + \frac{1}{\lambda}\,\right)\ \text{when the prediction is perfect / arbitrary respectively, and more precisely } \ \le\ \min!\Bigl(1 + \tfrac{1}{\lambda},\ \tfrac{(1+\lambda)\,}{}\Bigr) \text{ degrading smoothly with } \eta.$$

Read the tradeoff curve directly:

• As λ → 0 (full trust): consistency 1 + λ → 1 (optimal when the prediction is right), but robustness 1 + 1/λ → ∞ (catastrophic if it is wrong).
• As λ → 1 (full hedge): consistency 1 + λ → 2 and robustness 1 + 1/λ → 2 — you recover the deterministic online guarantee, having thrown the prediction away.

So λ slides continuously along the consistency–robustness Pareto frontier: every point trades how much a good prediction helps against how much a bad one hurts. The engineer picks λ from the measured reliability of the predictor.

The randomized learning-augmented algorithm¶

PSK also give a randomized version that combines the truncated-geometric buy-day schedule with the prediction, achieving a strictly better frontier:

Theorem (PSK 2018, randomized). There is a randomized learning-augmented ski-rental algorithm that is λ/(1 − e^{−λ})-consistent and 1/(1 − e^{−λ})-robust.

As λ → 0 the consistency λ/(1 − e^{−λ}) → 1 (perfect exploitation), and the robustness 1/(1 − e^{−λ}) grows controllably; as λ → 1 both approach the e/(e−1)-flavored online guarantee. The randomized frontier dominates the deterministic one — the same e/(e−1) magic that helped the prediction-free problem also sharpens the prediction-augmented tradeoff.

Why this is the seminal example¶

Ski rental was the perfect launchpad for learning-augmented algorithms because (a) its prediction is a single scalar D, so "prediction error η" is unambiguous; (b) its consistency/robustness curve has a clean closed form; and (c) the λ-dial generalizes — the same consistency-vs-robustness template now structures learning-augmented results for caching, scheduling, matching, and bipartite allocation. When a senior engineer hears "algorithm with predictions," the mental model is this ski-rental tradeoff curve. The discipline it instills: never trust a predictor blindly; expose a robustness dial λ so that a wrong prediction degrades you to the prediction-free competitive ratio, not to disaster.

Decision Framework¶

Research Pointers¶

• Karlin, A., Manasse, M., McGeoch, L., & Owicki, S. (1994). "Competitive Randomized Algorithms for Nonuniform Problems." Algorithmica. The randomized ski-rental algorithm and the e/(e−1) bound in their original form.
• Buchbinder, N., & Naor, J. (2009). "The Design of Competitive Online Algorithms via a Primal–Dual Approach." Foundations and Trends in TCS. The online primal–dual framework; ski rental as the canonical covering-LP example deriving both 2 and e/(e−1).
• Karlin, A., Kenyon, C., & Randall, D. (2001). "Dynamic TCP Acknowledgment and Other Stories about e/(e−1)." Algorithmica / STOC 2001. The TCP-acknowledgment problem, its e/(e−1) randomized optimality, and the Yao lower bound.
• Fleischer, R. (2001). "On the Bahncard Problem." Theoretical Computer Science. The discount-card generalization; 2-competitive deterministic and the e/(e−1+β) randomized bound.
• Meyerson, A. (2005). "The Parking Permit Problem." FOCS. Multi-option leasing; O(K) deterministic and O(log K) randomized, with matching lower bounds.
• Purohit, M., Svitkina, Z., & Kumar, R. (2018). "Improving Online Algorithms via ML Predictions." NeurIPS. The seminal learning-augmented paper; ski rental's (1+λ)-consistency / (1+1/λ)-robustness frontier.
• Mahdian, M., Nazerzadeh, H., & Saberi, A. (2012). "Online Optimization with Uncertain Information." ACM TALG. Early online-algorithm-plus-prediction model, a precursor to the learning-augmented framework.
• Gupta, A., Kumar, A., Pál, M., & Roughgarden, T. (2007). "Approximation via Cost Sharing: Simpler and Better Approximation Algorithms for Network Design." JACM. Single-source and Steiner rent-or-buy; sample-and-augment.
• Awerbuch, B., & Azar, Y. (1997). "Buy-at-Bulk Network Design." FOCS. The economies-of-scale rent-or-buy network primitive.
• Borodin, A., & El-Yaniv, R. (1998). Online Computation and Competitive Analysis. Cambridge Univ. Press. Ski rental, the rent-or-buy family, and Yao-based lower bounds in textbook form.

Key Takeaways¶

1. The e/(e−1) randomized algorithm is provably optimal. Yao's principle with a geometric hard distribution over the season length forces every deterministic buy-day to expected ratio e/(e−1) (via (1 − 1/B)^B → 1/e), lower-bounding every randomized algorithm. Algorithm and lower bound share the same geometric balance.
2. Ski rental is a covering LP. Constraints x + z_i ≥ 1 (cover each day by buying or renting) with the packing dual Σ y_i ≤ B, y_i ≤ 1. Weak duality DUAL ≤ OPT turns dual feasibility into a competitive guarantee — the foundation of the whole derivation.
3. The online primal–dual framework (Buchbinder–Naor) derives both algorithms mechanically. Raise primal and dual in lockstep with an exponential update rule; the additive-boost coefficient is the single dial that tunes the constant from the deterministic 2 to the randomized e/(e−1). Reading the primal variable as a threshold gives 2; reading it as a probability gives the truncated-geometric buy schedule and e/(e−1).
4. The rent-or-buy family all inherits ski rental's 2 / e/(e−1) signature. TCP acknowledgment (Karlin–Kenyon–Randall, e/(e−1) tight); Bahncard (Fleischer, 2 det / e/(e−1+β) rand); multi-shop, single-source/Steiner rent-or-buy and buy-at-bulk network design (constant-competitive by composing per-edge ski-rental decisions).
5. Parking permit (Meyerson) is multi-option ski rental. A menu of K lease durations yields O(K)-competitive deterministic and O(log K)-competitive randomized algorithms (both tight) — the underlying primitive for online leasing of facilities, Steiner trees, and set cover.
6. Learning-augmented ski rental (Purohit–Svitkina–Kumar 2018) launched algorithms-with-predictions. A trust dial λ trades (1+λ)-consistency (ratio → 1 as prediction error → 0) against (1+1/λ)-robustness (bounded ratio even on arbitrary predictions); the randomized version sharpens the frontier to λ/(1−e^{−λ}) consistency, 1/(1−e^{−λ}) robustness. Always expose λ so a wrong prediction degrades you to the prediction-free ratio, never to disaster.

See also: ./middle.md for the break-even algorithm, the e/(e−1) schedule, and the Bahncard statement · ./professional.md for engineering rent-or-buy decisions in real systems · ../01-competitive-analysis/senior.md for Yao's principle and the potential method · ../03-paging-and-caching-theory/senior.md for the H_k Yao lower bound, ski rental's caching cousin