de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Impressum Kontakt Einloggen
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Bericht

On the Bahncard problem

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44431

Fleischer,  Rudolf
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)

1997-1-018
(beliebiger Volltext), 11KB

Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Fleischer, R.(1997). On the Bahncard problem (MPI-I-1997-1-018). Saarbrücken: Max-Planck-Institut für Informatik.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-0014-9D7F-F
Zusammenfassung
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.