Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society


On the Bahncard problem

Fleischer, Rudolf

MPI-I-97-1-018. September 1997, 16 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:

In this paper, we generalize the {\em Ski-Rental Problem}
to the {\em Bahncardproblem} which is an online problem of
practical relevance for all travelers.
The Bahncard is a railway pass of the Deutsche Bundesbahn (the German
railway company) which entitles its holder to a 50\%\ price
reduction on nearly all train tickets.
It costs 240\thinspace DM, and it is valid for 12 months.

For the common traveler, the decision at which time to buy
a Bahncard is a typical online problem, because she usually does
not know when and where to she will travel next.
We show that the greedy algorithm applied by most travelers
and clerks at ticket offices is not better in the worst case
than the trivial algorithm which never buys a Bahncard.
We present two optimal deterministic online algorithms,
an optimistic one and and a pessimistic one.
We further give a lower bound for randomized online algorithms
and present an algorithm which we conjecture to be optimal;
a proof of the conjecture is given for a special case of the problem.
It turns out that the optimal competitive ratio only depends on
the price reduction factor (50\%\ for the German Bahncardproblem),
but does not depend on the price or validity period of a Bahncard.
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-97-1-018.ps146 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document:

Hide details for BibTeXBibTeX
  AUTHOR = {Fleischer, Rudolf},
  TITLE = {On the Bahncard problem},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-97-1-018},
  MONTH = {September},
  YEAR = {1997},
  ISSN = {0946-011X},