In
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, 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.
The problem
Many
online problem
In computer science, an online algorithm is one that can process its input piece-by-piece in a serial fashion, i.e., in the order that the input is fed to the algorithm, without having the entire input available from the start.
In contrast, an o ...
s 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.
[Steven S. Seiden. A guessing game and randomized online algorithms. Annual ACM Symposium on Theory of Computing, 2000. http://portal.acm.org/citation.cfm?id=335385] Ski rental
[ A. R. Karlin, M. S. Manasse, L. A. McGeoch, and S. Owicki. Competitive randomized algorithms for non-uniform problems. In Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, 22–24 January 1990, pp. 301-309. Also in Algorithmica, 11(6): 542-571, 1994. http://courses.csail.mit.edu/6.895/fall03/handouts/papers/karlin.pdf] 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 do when she does not know in advance how many days one will ski?
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).
The break-even algorithm
The break-even algorithm instructs one to rent for 9 days and buy skis on the morning of day 10 if one are still up for skiing.
[ A. R. Karlin, M. Manasse, L. Rudolph and D. Sleator. Competitive snoopy caching. Algorithmica, 3(1): 79-119, 1988] If one have 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 have 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.
The randomized algorithm
A person can flip a coin. If it comes up heads, she buy skis on day eight; otherwise, she buys skis on day 10. This is an instance of a
randomized algorithm
A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic or procedure. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performan ...
. 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
+10+ 1/2
+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 expected
competitive ratio Competitive analysis is a method invented for analyzing online algorithms, in which the performance of an online algorithm (which must satisfy an unpredictable sequence of requests, completing each request without being able to see the future) is co ...
on a given instance i as:
, where
is the competitive ratio for instance i, given
.
Consequently, the competitive ratio of a randomized algorithm is given by the worst value of
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
and
, respectively.
, for
.
,
, and
, for
.
Therefore, the competitive ratio of the randomized ski-rental coin flipping algorithm is 1.8.
The best randomized algorithm against an
oblivious 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.
first presented this algorithm with distribution
where buying skis costs $
and renting costs $1. Its expected cost is at most e/(e-1)
1.58 times what one would pay if one had known the number of days one would go skiing. No randomized algorithm can do better.
Applications
*
Snoopy caching:
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: 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.
[ Anna R. Karlin and Claire Kenyon and Dana Randall. Dynamic TCP acknowledgement and other stories about e/(e-1). Thirty-Third Annual ACM Symposium on Theory of Computing (STOC), 2001. Algorithmica. http://www.cs.brown.edu/people/claire/Publis/ACKpaper.ps] 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
Total may refer to:
Mathematics
* Total, the summation of a set of numbers
* Total order, a partial order without incomparable pairs
* Total relation, which may also mean
** connected relation (a binary relation in which any two elements are comp ...
:
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.
See also
*
Adversary (online algorithm)
*
Competitive analysis (online algorithm) Competitive analysis is a method invented for analyzing online algorithms, in which the performance of an online algorithm (which must satisfy an unpredictable sequence of requests, completing each request without being able to see the future) is co ...
*
Online algorithm
In computer science, an online algorithm is one that can process its input piece-by-piece in a serial fashion, i.e., in the order that the input is fed to the algorithm, without having the entire input available from the start.
In contrast, an o ...
*
Optimal stopping
In mathematics, the theory of optimal stopping or early stopping
: (For French translation, secover storyin the July issue of ''Pour la Science'' (2009).) is concerned with the problem of choosing a time to take a particular action, in order to ...
Worst-case proof
References
{{Reflist, colwidth=30em
Online algorithms