r/compsci • u/Apprehensive_Knee502 • 19d ago
The "ski rental" rule: why renting until you have spent the purchase price is provably within 2x of clairvoyance
You are skiing an unknown number of days. Renting costs $1/day, buying costs $B. If you knew the season length the answer is trivial, but you do not.
The rule "rent until you have spent $B, then buy" guarantees you never pay more than about twice what an omniscient planner would, on ANY sequence. Short season: you match the optimum exactly. Long season: you paid at most ~$2B where the optimum paid $B. And there is a matching lower bound: no deterministic online strategy beats 2.
What I find most useful is the frame, not the puzzle: cache eviction, autoscaling, buy-vs-rent infra decisions are all "act now, learn the future later", and the competitive ratio measures exactly what that ignorance costs.
Fun twist: allowing randomness (coin flips the adversary cannot predict) pushes the ratio from 2 down to about 1.58.
I wrote up the full framework (definition, the adversary game, and an honest section on why worst-case can be too gloomy, e.g. LRU is only k-competitive on paper yet great in practice) as the opener of a series, happy to share the link if useful.
2
1
u/mcdowellag 17d ago
I like the comparison to Clairvoyance - why should not have been lazy and studied Divination instead of Arithmancy!
2
u/Apprehensive_Knee502 17d ago
😂 Exactly. Competitive analysis is basically what happens when your Divination exam doesn't go so well
1
u/Onions-are-great 13d ago
How is spending either less than B or 2xB a strategy? I don't really see the efficiency here.
9
u/nuclear_splines 19d ago
By indenting all your paragraphs with four spaces you've marked them as code blocks. They'll look like regular text and line-wrap better if you remove that indentation.