×

On the Bahncard problem. (English) Zbl 0984.68194

Summary: In this paper, we generalize the Ski-Rental Problem to the Bahncard Problem 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\) DM, and it is valid for 12 months. Similar bus or railway passes can be found in many other countries. 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 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 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 Bahncard Problem), but does not depend on the price or validity period of a Bahncard.

MSC:

68W05 Nonnumerical algorithms
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] S. Albers, H. Koga, New on-line algorithms for the page replication problem, J. Algorithms 27(1) (1998) 75-96. A preliminary version was published in Proc. 4th Scandinavian Workshop on Algorithm Theory (SWAT’94), Lecture Notes in Computer Science, vol. 824, Springer, Berlin, 1994, pp. 25-36. · Zbl 0919.68049
[2] Y. Azar, Y. Bartal, E. Feuerstein, A. Fiat, S. Leonardi, A. Rosén, On capital investment, Proc. 23rd Internat. Colloquium on Automata, Languages and Programming (ICALP’96), Lecture Notes in Computer Science, vol. 1099, Springer, Berlin, 1996, pp. 429-441. · Zbl 1045.90518
[3] Ben-David, S.; Borodin, A.; Karp, R.; Tardos, G.; Wigderson, A., On the power of randomization in on-line algorithms, Algorithmica, 11, 1, 2-14, (1994) · Zbl 0784.68038
[4] D.L. Black, D.D. Sleator, Competitive algorithms for replication and migration problems, Tech. Rep. CMU-CS-89-201, Carnegie Mellon University, 1989.
[5] Johnson, D.S.; Demers, A.; Ullman, J.D.; Garey, M.R.; Graham, R.L., Worst-case performance bounds for simple one-dimensional packing algorithms, SIAM J. comput., 3, 4, 299-325, (1974) · Zbl 0297.68028
[6] A.R. Karlin, M.S. Manasse, L.A. McGeoch, S. Owicki, Competitive randomized algorithms for non-uniform problems, Proc. 1st ACM-SIAM Symp. on Discrete Algorithms (SODA’90), 1990, pp. 301-309. · Zbl 0800.68456
[7] Karlin, A.R.; Manasse, M.S.; Rudolph, L.; Sleator, D.D., Competitive snoopy caching, Algorithmica, 3, 1, 79-119, (1988) · Zbl 0645.68034
[8] C. Lund, N. Reingold, J. Westbrook, D. Yan, On-line distributed data management, Proc. 2nd European Symp. on Algorithms (ESA’94), Lecture Notes in Computer Science, vol. 855, Springer, Berlin, 1994, pp. 202-214. · Zbl 0933.68152
[9] P. Raghavan, Lecture notes on randomized algorithms, Tech. Rep. RC 15340 1/9/90, IBM Research Division, T.J. Watson Research Center, Yorktown Heights, New York, 1990.
[10] P. Raghavan, M. Snir, Memory versus randomization in on-line algorithms, Proc. 16th Internat. Colloquium on Automata, Languages and Programming (ICALP’89), Lecture Notes in Computer Science, vol. 372, Springer, Berlin, 1989, pp. 687-703.
[11] Sleator, D.D.; Tarjan, R.E., Amortized efficiency of List update and paging rules, Comm. ACM, 28, 2, 202-208, (1985)
[12] R.E. Tarjan, Data Structures and Network Algorithms, CBMS-NSF Regional Conference Series in Applied Mathematics, SIAM, Philadelphia, PA, 1983. · Zbl 0584.68077
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.