| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 428612 | Information Processing Letters | 2011 | 4 Pages |
We propose the ski-rental problem with multiple discount options in which there are n options to rent an equipment. Every option has a rental duration; the longer the duration, the more the discount. This generalizes the standard ski-rental problem where one can only rent or buy. We present a 4-competitive on-line algorithm for our problem and show that no deterministic algorithm can have a smaller competitive ratio when n is large enough. Comparing with the original ski-rental problem, the competitive ratio becomes larger when there are more options.
► We generalize the classic ski-rental problem to have multiple options. ► We give a 4-competitive on-line algorithm. ► We prove a matching lower bound for all deterministic on-line algorithms.
