@techreport{Fleischer97,
TITLE = {On the Bahncard problem},
AUTHOR = {Fleischer, Rudolf},
LANGUAGE = {eng},
URL = {http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1997-1-018},
NUMBER = {MPI-I-1997-1-018},
INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
ADDRESS = {Saarbr{\"u}cken},
YEAR = {1997},
DATE = {1997},
ABSTRACT = {In this paper, we generalize the {\em Ski-Rental Problem}<br>to the {\em Bahncardproblem} which is an online problem of<br>practical relevance for all travelers.<br>The Bahncard is a railway pass of the Deutsche Bundesbahn (the German<br>railway company) which entitles its holder to a 50\%\ price<br>reduction on nearly all train tickets.<br>It costs 240\thinspace DM, and it is valid for 12 months.<br><br>For the common traveler, the decision at which time to buy<br>a Bahncard is a typical online problem, because she usually does<br>not know when and where to she will travel next.<br>We show that the greedy algorithm applied by most travelers<br>and clerks at ticket offices is not better in the worst case<br>than the trivial algorithm which never buys a Bahncard.<br>We present two optimal deterministic online algorithms,<br>an optimistic one and and a pessimistic one.<br>We further give a lower bound for randomized online algorithms <br>and present an algorithm which we conjecture to be optimal;<br>a proof of the conjecture is given for a special case of the problem. <br>It turns out that the optimal competitive ratio only depends on<br>the price reduction factor (50\%\ for the German Bahncardproblem),<br>but does not depend on the price or validity period of a Bahncard.},
TYPE = {Research Report / Max-Planck-Institut für Informatik},
}