Ski rental problem

from Wikipedia, the free encyclopedia
The following important information is missing from this article or section:
Mathematical intuition and problem solving
Help Wikipedia by researching and pasting it .

The ski rental problem is about deciding at the right time to buy skis once or to rent them for every ski run, provided that the total costs are minimal. It was once created as an educational tool for understanding online algorithms . The ski rental problem is representative of a number of problems in which a consumer wants to practice a sport (e.g. cycling , surfing , tennis ) for which a piece of sports equipment is required (e.g. bicycle , surfboard , Tennis racket ), which can either be bought once or borrowed several times.

Problem Description

For example, suppose someone who doesn't own skis wants to go skiing. He has the choice between buying a pair of skis (once) (purchase price e.g. 200 euros) and renting them (daily rental e.g. 20 euros). If he already knows at the beginning that he only wants to drive for five days, the rent is cheaper than buying (5 × 20 <200). If, on the other hand, he wanted to ski for 12 days, it would be smarter to buy the pair of skis on the first day, as buying them for 200 euros is cheaper than renting them for 12 days (12 × 20 euros = 240 euros).

We are now looking for a rule to act (an algorithm) in the event that one does not know the number of skiing days at the beginning. The algorithm aims to minimize the relative additional costs that can arise from not knowing the number of future skiing days. It is easy to show that if you buy the pair of skis on the morning of the 10th day, in the worst case the costs are 90% higher than if you knew the number of skiing days from the start.

literature

  • Mark S. Manasse: Ski Rental Problem . In: Ming-Yang Kao (ed.): Encyclopedia of Algorithms . Springer, Berlin / Heidelberg / New York 2008, ISBN 978-0-387-30162-4 , part 18.
  • Anna R. Karlin: On the Performance of Competitive Algorithms in Practice . In: Amos Fiat, Gerhard J. Woeginger (ed.): Online Algorithms. The State of the Art. Lecture Notes in Computer Science 1442 , Springer, Berlin / Heidelberg / New York 2008, ISBN 3-540-64917-4 , chap. 16, p. 373 ff.