Abstract
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.
| Original language | English |
|---|---|
| Pages (from-to) | 903-906 |
| Number of pages | 4 |
| Journal | Information Processing Letters |
| Volume | 111 |
| Issue number | 18 |
| DOIs | |
| State | Published - 30 Sep 2011 |
Keywords
- Competitive analysis
- Lower bound
- Multiple options
- On-line algorithms
- Ski-rental problem
Fingerprint
Dive into the research topics of 'The ski-rental problem with multiple discount options'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver