The "ski rental" rule: why renting until you have spent…
0 reactions
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.
#technology
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.
#technology
| 3,000 mlx | |
| 4 | |
| 0 |