Risk Management for Online Simplified Bahncard Problem
Chunlin Xin, Wentian Cui, Weimin Ma · 2006
The Bahncard problem is a generalization of the Ski-Rental problem. Previous research approaches on the Bahncard problem have mostly focused on the "pure" competitive analysis that "deliberately" ignores all available information. Fleischer presented a deterministic (2-beta)-competitive online algorithm and showed that this is the best competitiveness of a deterministic strategy for the BP (C,beta,T). Recently Karlin, Kenyon and Randall developed a randomized on-line algorithm that achieves an optimal competitive ratio of (e/(e-1))~1.58. In this paper, risk management is introduced to restudy the simplified Bahncard problem and the research results show that the performance measure of competitive analysis can be dramatically improved