English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
  On the Bahncard problem

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

Item is

Files

show Files
hide Files
:
1997-1-018 (Any fulltext), 11KB
Name:
1997-1-018
Description:
-
OA-Status:
Visibility:
Public
MIME-Type / Checksum:
text/html / [MD5]
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show

Creators

show
hide
 Creators:
Fleischer, Rudolf1, Author           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 Abstract: 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.

Details

show
hide
Language(s): eng - English
 Dates: 1997
 Publication Status: Issued
 Pages: 16 p.
 Publishing info: Saarbrücken : Max-Planck-Institut für Informatik
 Table of Contents: -
 Rev. Type: -
 Identifiers: URI: http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1997-1-018
Report Nr.: MPI-I-1997-1-018
BibTex Citekey: Fleischer97
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: Research Report / Max-Planck-Institut für Informatik
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: - Identifier: -