The classic introductory example of an online algorithm. The problem (described below) is not too hard to solve; it's the formulation that was hard to come up with. There's also a spoiler under Ski Rental Problem solution. I've never gone skiing, though, so the prices below may be all wrong.

You're on your first-ever ski holiday. You arrive at the Chateau Ripoffe resort for a potentially unlimited period, sans skis. You determine to go skiing every day, as long as the weather permits, and then go home. Every morning, you may decide to buy a pair of skis (for \$150) or rent them for one day (for \$10). Obviously, you'd like the whole experience to be as cheap as possible. What to do?

If you have no reliable probabilistic prediction of the weather, one way to go about this is through competitive analysis: show that your strategy is never worse than c times as bad as the best thing you could have done. Try and find a "c-competitive" algorithm to solve the Ski Rental Problem. Is the competitive ratio you found (c) the best possible?

If you're not sure, or you'd rather just peek at the answer, head for Ski Rental Problem solution.

A more general form of this problem is the German Bahncard Problem, in which a train traveller must consider when to purchase a discount card, valid for a given period, as his train-travel needs arise.

Log in or register to write something here or to contact authors.