In this paper, we generalize the Ski-Rental Problem to the Bahncard Problem
which is an online problem of practical relevance for all travelers, The B
ahncard is a railway pass of the Deutsche Bundesbahn (the German railway co
mpany) which entitles its holder to a 50% price reduction on nearly all tra
in tickets. It costs 240 DM, and it is valid for 12 months. Similar bus or
railway passes can be found in many other countries. For the common travele
r, the decision at which time to buy a Bahncard is a typical online problem
, because she usually does not know when and where she will travel next. We
show that the greedy algorithm applied by most travelers and clerks at tic
ket offices is not better in the worst case than the trivial algorithm whic
h never buys a Bahncard. We present two optimal deterministic online algori
thms, an optimistic one and a pessimistic one. We further give a lower boun
d for randomized online algorithms and present an algorithm which we conjec
ture to be optimal; a proof of the conjecture is given for a special case o
f the problem. It turns out that the optimal competitive ratio only depends
on the price reduction factor (50% for the German Bahncard Problem), but d
oes not depend on the price or validity period of a Bahncard. (C) 2001 Else
vier Science B.V. All rights reserved.