Skip to content

CONCEPT Cited by 1 source

Ski-rental problem

Definition

The ski-rental problem is the canonical toy problem in online algorithm theory for modelling rent-vs-buy decisions under uncertainty. The setup: you're going skiing for an unknown number of days. Renting costs $1/day; buying costs $B. When should you stop renting and buy?

The breakeven strategy — rent for B−1 days then buy on day B — is 2-competitive: in the worst case you pay at most twice what the optimal offline algorithm (which knows the total number of ski days in advance) would pay. A randomized variant achieves e/(e−1) ≈ 1.58-competitive against an oblivious adversary.

Application to caching

In elastic caching, each cached page faces a ski-rental decision:

  • Rent = keep the page in memory, paying memory cost per time unit (size × time)
  • Buy = evict the page, paying the miss cost next time it's accessed

The breakeven TTL is set at the point where cumulative memory rental cost equals the expected miss cost. This maps the caching problem into a well-studied theoretical framework with known competitive-ratio guarantees.

(Source: sources/2026-06-25-google-optimizing-cloud-economics-with-linear-elastic-caching)

Properties

  • 2-competitive (deterministic): worst-case cost is at most 2× optimal
  • e/(e−1)-competitive (randomized): ≈1.58× optimal against oblivious adversary
  • Online: decisions are irrevocable and made without future knowledge
  • Generalizes to: TCP acknowledgment, snoopy caching, online replacement, dynamic resource provisioning

Seen in

Last updated · 559 distilled / 1,651 read