Ski rental problem - Wikipedia

submited by

Style Pass

2021-06-11 15:00:07

In computer science, the ski rental problem is a name given to a class of problems in which there is a choice between continuing to pay a repeating cost or paying a one-time cost which eliminates or reduces the repeating cost.

Many online problems have a sub-problem called the rent/buy problem. We need to decide whether to stay in the current state and pay a certain amount of cost per time unit, or switch to another state and pay some fixed large cost with no further payment.[1] Ski rental[2][3] is one example where the rent/buy is the entire problem. Its basic version is:

A person is going skiing for an unknown number of days. Renting skis costs $1 per day and buying skis costs $10. Every day, the person must decide whether to continue renting skis for one more day or buy a pair of skis. If the person knows in advance how many days she will go skiing, she can decide her minimum cost. If she will be skiing for more than 10 days it will be cheaper to buy skis but if she will be skiing for fewer than 10 days it will be cheaper to rent. What should she when she does not know in advance how many days one will ski?[citation needed ]

Formally, the problem can be set up as follows. There is a number of days d (unknown) that the person will ski. The goal is to find algorithm that minimizes the ratio between what the person pay using the algorithm (that does not know d) and what the person would pay optimally if the person knew d in advance. The problem is generally analyzed in the worst case, where the algorithm is fixed and then we look at the worst-case performance of the algorithm over all possible d. In particular, no assumptions are made regarding the distribution of d (and it is easy to see that, with knowledge of the distribution of d, a different analysis as well as different solutions would be preferred).[citation needed ]