This article has multiple issues. Please helpimprove it or discuss these issues on thetalk page.(Learn how and when to remove these messages) This articlemay be too technical for most readers to understand. Pleasehelp improve it tomake it understandable to non-experts, without removing the technical details.(July 2020) (Learn how and when to remove this message) This articleneeds additional citations forverification. Please helpimprove this article byadding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Ski rental problem" – news ·newspapers ·books ·scholar ·JSTOR(July 2020) (Learn how and when to remove this message) (Learn how and when to remove this message)

Incomputer science, theski 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.^[1]

This sectionneeds additional citations forverification. Please helpimprove this article byadding citations to reliable sources in this section. Unsourced material may be challenged and removed.(July 2020) (Learn how and when to remove this message)

Manyonline problems have a sub-problem called the rent-or-buy problem. Given an expensive up front cost, or a less expensive repeating cost, with no knowledge of how the future will play out, at what point is it better to pay the up front cost to avoid a continued repeating cost?

Consider a person who decides to go skiing, but for an undecided number of days. Renting skis costs $1 per day, whereas buying a pair of skis costs $10. If the person knows in advance how many days they want to ski, then the breakeven point is 10 days. Fewer than 10 days, renting is preferable, whereas with more than 10 days, buying is preferable. However, with no advance knowledge of how long one will be skiing, the breakeven point is unclear. A good algorithm will minimize the ratio of the cost when the number of days is known in advance to the cost when the number of days is not known in advance.^[2] Ski rental^[3][4] is one example of this class of problem.

This sectionneeds additional citations forverification. Please helpimprove this article byadding citations to reliable sources in this section. Unsourced material may be challenged and removed.(July 2020) (Learn how and when to remove this message)

The break-even algorithm instructs one to rent for 9 days and buy skis on the morning of day 10 if one is still up for skiing.^[5] If one has to stop skiing during the first 9 days, it costs the same as what one would pay if one had known the number of days one would go skiing. If one has to stop skiing after day 10, one's cost is $19 which is 90% more than what one would pay if one had known the number of days one would go skiing in advance. This is the worst case for the break-even algorithm.

The break-even algorithm is known to be the best deterministic algorithm for this problem.

This sectionneeds additional citations forverification. Please helpimprove this article byadding citations to reliable sources in this section. Unsourced material may be challenged and removed.(July 2020) (Learn how and when to remove this message)

A person can flip a coin. If it comes up heads, she buys skis on day eight; otherwise, she buys skis on day 10. This is an instance of arandomized algorithm. The expected cost is at most 80% more than what the person would pay if she had known the number of days she would go skiing, regardless of how many days she skis. In particular, if the person skis for 10 days, her expected cost is 1/2 [7 +10] + 1/2 [9+10] = 18 dollars, only 80% excess instead of 90%.

A randomized algorithm can be understood as a composition of different algorithms, each one which occurs with a given probability. We define the expectedcompetitive ratio on a given instance i as:

${\displaystyle E_i=\sum _{j}P(AL{G}_j)\cdot AL{G}_j(i)}$, where${\displaystyle AL{G}_j(i)}$ is the competitive ratio for instance i, given${\displaystyle AL{G}_j}$.

Consequently, the competitive ratio of a randomized algorithm is given by the worst value of${\displaystyle E_i}$ over all given instances. In the case of the coin flipping ski-rental, we note that the randomized algorithm has 2 possible branches: If the coin comes up heads, we buy on day 8, otherwise we buy on day 10. We may call the branches${\displaystyle AL{G}_{heads}}$ and${\displaystyle AL{G}_{tails}}$, respectively.${\displaystyle E_i=P(AL{G}_{heads})\cdot AL{G}_{heads}(i)+P(AL{G}_{tails})\cdot AL{G}_{tails}(i)=\frac{1}{2}\cdot 1+\frac{1}{2}\cdot 1=1}$, for.

${\displaystyle E_8=P(AL{G}_{heads})\cdot AL{G}_{heads}(8)+P(AL{G}_{tails})\cdot AL{G}_{tails}(8)=\frac{1}{2}\cdot \frac{17}{8}+\frac{1}{2}\cdot 1=1.5625}$,

${\displaystyle E_9=P(AL{G}_{heads})\cdot AL{G}_{heads}(9)+P(AL{G}_{tails})\cdot AL{G}_{tails}(9)=\frac{1}{2}\cdot \frac{17}{9}+\frac{1}{2}\cdot 1=1.444444}$, and

${\displaystyle E_i=P(AL{G}_{heads})\cdot AL{G}_{heads}(i)+P(AL{G}_{tails})\cdot AL{G}_{tails}(i)=\frac{1}{2}\cdot \frac{17}{10}+\frac{1}{2}\cdot \frac{19}{10}=1.8}$, for${\displaystyle i\ge 10}$.

Therefore, the competitive ratio of the randomized ski-rental coin flipping algorithm is 1.8.

The best randomized algorithm against anoblivious adversary is to choose some day i at random according to the following distribution p, rent for i-1 days and buy skis on the morning of day i if one are still up for skiing. Karlin et al.^[3] first presented this algorithm with distributionwhere buying skis costs $${\displaystyle b}$ and renting costs $1. Its expected cost is at most e/(e-1)${\displaystyle \approx }$ 1.58 times (when b tends to infinity) what one would pay if one had known the number of days one would go skiing. No randomized algorithm can do better.

This sectionneeds additional citations forverification. Please helpimprove this article byadding citations to reliable sources in this section. Unsourced material may be challenged and removed.(July 2020) (Learn how and when to remove this message)

• Snoopy caching:^[3] several caches share the same memory space that is partitioned into blocks. When a cache writes to a block, caches that share the block spend 1 bus cycle to get updated. These caches can invalidate the block to avoid the cost of updating. But there is a penalty of p bus cycles for invalidating a block from a cache that shortly thereafter needs access to it. We can break the write request sequences for several caches into request sequences for two caches. One cache performs a sequence of write operations to the block. The other cache needs to decide whether to get updated by paying 1 bus cycle per operation or invalidate the block by paying p bus cycles for future read request of itself. The two cache, one block snoopy caching problem is just the ski rental problem.

• TCP acknowledgment:^[6] A stream of packets arrive at a destination and are required by the TCP protocol to be acknowledged upon arrival. However, we can use a single acknowledgment packet to simultaneously acknowledge multiple outstanding packets, thereby reducing the overhead of the acknowledgments. On the other hand, delaying acknowledgments too much can interfere with the TCP's congestion control mechanisms, and thus we should not allow the latency between a packet's arrival time and the time at which the acknowledgment is sent to increase too much. Karlin et al.^[7] described a one-parameter family of inputs, called the basis inputs, and showed that when restricted to these basis inputs, the TCP acknowledgement problem behaves the same as the ski rental problem.

• Total completion time scheduling:^[2] We wish to schedule jobs with fixed processing times on m identical machines. The processing time of job j is p_j. Each job becomes known to the scheduler on its release time r_j. The goal is to minimize the sum of completion times over all jobs. A simplified problem is one single machine with the following input: at time 0, a job with processing time 1 arrives; k jobs with processing time 0 arrive at some unknown time. We need to choose a start time for the first job. Waiting incurs a cost of 1 per time unit, yet starting the first job before the later k jobs may incur an extra cost of k in the worst case. This simplified problem may be viewed as a continuous version of the ski rental problem.

• Refactoring versus working with a poor design: In software development, engineers have to choose between the friction and risk of errors of working with an overly-complex design and reducing the complexity of the design before making a change. The extra cost of each change with the old design is the "rental" cost, the cost of refactoring is the "buy" cost. "How many times does one work with a poor design before cleaning it up?" is a ski rental problem.

• Adversary (online algorithm)
• Competitive analysis (online algorithm)
• Online algorithm
• Optimal stopping

• Online algorithms

• Wikipedia articles that are too technical from July 2020
• All articles that are too technical
• Articles needing additional references from July 2020
• All articles needing additional references
• Articles with multiple maintenance issues