Das BahnCard Problem

Ein typischer Bahnreisender weiß im voraus nicht genau, wie seine Reisepläne in Zukunft aussehen werden. Somit steht er häufig vor der Entscheidung, eine BahnCard zu kaufen oder eben nicht zu kaufen. Am Ende einer Zeitperiode stellt sich im nachhinein heraus, welche Entscheidungen für den Reisenden optimal gewesen wäre. Es wird gezeigt, daß jeder Reisende gegenüber der optimalen Lösung zu einem faktoriellen Aufpreis gezwungen werden kann und daß es Entscheidungsstrategien gibt, die genau diesen best möglichen Faktor erzielen.

Inhalt des Vortrags:

• Vorstellung des Problems
• Optimaler Offline Algorithmus (Theorem 2)
• Deterministischer Online Algorithmus
  • Untere Schranke (Theorem 3)
  • Optimaler Algorithmus SUM (Theorem 4)
  • Optimaler Algorithmus OSUM (Theorem 5) [optional]

Literatur:
On the Bahncard Problem
Rudolf Fleischer, MPI-Forschungsbericht, MPI-I-97-1-018, September 1997
S. 1-16, relevant S. 1-11.

Betreuer:
Elmar Langetepe