Ski-Rental-Problem

Das Ski-Rental-Problem (Skiverleihproblem) beschreibt die Problemstellung, die beim Design von Online-Algorithmen entsteht. In dem konkreten Problem geht es darum, zu einem passenden Zeitpunkt zu entscheiden, Skier einmalig zu kaufen oder für jeden Skilauf zu leihen, und zwar unter der Maßgabe, dass die Gesamtkosten minimal sind. Das Ski-Rental-Problem steht stellvertretend für eine Reihe von Problemen, in denen jeweils ein Konsument etwas einmalig kauft zu einem festen Preis oder leihweise für die genutzte Zeit bezahlt. Dabei ist stets unklar, wie lang das Problem läuft, das heißt es muss jeden Tag neu entschieden werden, ob es sich nun lohnt zu kaufen oder weiter zu leihen.

Problembeschreibung

Wir nehmen an, eine Person ohne Ski möchte Ski fahren gehen. Sie hat die Wahl zwischen dem (einmaligen) Kauf eines Paares Skier (Kaufpreis z. B. 200 Euro) und der Miete (Tagesmiete z. B. 20 Euro). Entscheidend ist, dass die Person nicht weiß, wie lange sie Skifahren wird, sondern jeden Tag neu entscheiden kann, ob es sich nun lohnt zu kaufen oder weiter zu mieten. Dies modelliert ein typisches Online-Problem, bei dem der Input (Wie viele Tage fahre ich Ski?) erst mit der Zeit bekannt wird.

Der Offline-Fall beschreibt das Problem, wenn die Person schon weiß, dass sie nur eine feste Zahl Tage fahren will. In diesem Fall ist einfach auszurechnen, ob kaufen oder mieten billiger ist. Wenn beispielsweise fünf Tage Ski fahren geplant sind, kommt die Miete von Euro günstiger als ein Kauf von Euro. Sind hingegen zwölf Tage Ski fahren geplant, ist es billiger, gleich am ersten Tag das Paar Skier zu kaufen, da der Kauf für Euro günstiger ist als die Miete von Euro.

Gesucht ist nun eine Handlungsvorschrift (ein Algorithmus) für den Fall, dass man die Anzahl Skitage am Anfang nicht kennt. Der Algorithmus soll die relativen Zusatzkosten minimieren, die durch die Unkenntnis der Anzahl zukünftiger Skitage entstehen können. Für die angenommenen Preise lässt sich zeigen, dass wenn man am Morgen des 10. Tages das Paar Skier kauft, die Kosten im schlimmsten Fall 90 % höher liegen, als wenn man die Anzahl Skitage von Anfang an wüsste. Dies beschreibt die Kompetitivität des Algorithmus.

Siehe auch

Literatur

  • Mark S. Manasse: Ski Rental Problem. In: Ming-Yang Kao (Hg.): Encyclopedia of Algorithms. Springer, Berlin/Heidelberg/New York 2008, ISBN 978-0-387-30162-4, Teil 18.
  • Anna R. Karlin: On the Performance of Competitive Algorithms in Practice. In: Amos Fiat, Gerhard J. Woeginger (Hg.): Online Algorithms. The State of the Art. Lecture Notes in Computer Science 1442, Springer, Berlin/Heidelberg/New York 2008, ISBN 3-540-64917-4, Kap. 16, S. 373 ff.