Abstract
The special Bahncard problem is the generalization of the Ski-Rental problem. In this paper, the average-case competitive analysis that integrates probability distribution into pure competitive analysis is employed to restudy this problem. Theoretical and numerical results show that the performance measure of competitive analysis can be dramatically improved. Moreover, considering the interest rate is an essential feature of any reasonable financial model and the special Bahncard problem with interest rate is discussed. The different competitive ratios in two cases are obtained, and the competitive ratio decreases with the interest rate.
| Original language | English |
|---|---|
| Pages (from-to) | 84-92 |
| Number of pages | 9 |
| Journal | Xitong Gongcheng Lilun yu Shijian/System Engineering Theory and Practice |
| Volume | 27 |
| Issue number | 10 |
| State | Published - Oct 2007 |
Keywords
- Competitive algorithms
- Competitive ratio
- Probability distribution
- Special Bahncard problem