Ski-Rental-Problem

When Ski -Rental problem it comes to decide on an appropriate time, skis to buy one or to borrow for each ski, under the proviso that the total cost is minimal. It was once used as an educational tool for the understanding of online algorithms. The Ski -Rental problem is representative of a number of problems, in each of which a consumer wishes to pursue a sport (eg, cycling, surfing, tennis), for a sports equipment is required (eg, bicycle, surfboard, tennis rackets ), which can be bought or borrowed either unique.

SYMPTOMS

Suppose a person who does not want to ski, go Skiing. The person has the option to choose between the one-time purchase of a pair of skis (purchase price eg 200 euros ) and the loan of a pair for every skiing ( eg, Rental price 20 euros ) to choose. If the person is known at the beginning the number of ski runs (eg, 5 runs), the decision would fall in the case of the example of the five-time loan, since the rental cost in the amount of 5 × 20 € = 100 € would be lower than the purchase price. If the person on the other hand want to travel for 12 days of ski, it would be smart for them to on the first day to buy the pair of skis, since the purchase cost of 200 euros less than the rental cost for 12 days (12 * 20 € = 240 € ). The goal here now is to find an action rule ( algorithm), which is to minimize the additional costs that may arise due to ignorance about the number of ski days. It is easy to show that if you are in the morning of the 10th day buys the pair of skis, the additional cost in the worst case are 90 % higher than if you would know how long it would go skiing.