スキーレンタル問題：最適コストのためのランダム化アルゴリズム

この記事では、オンラインアルゴリズムにおける興味深い例題である、古典的なスキーレンタル問題を取り上げます。問題：スキーヤーはスキーをする日数がわかりません。レンタルは1日あたり1単位のコスト、購入はB単位のコストがかかります。この記事では、最適なオフラインソリューションの詳細を示し、その後、競合比が2のシンプルなオンラインアルゴリズムを分析します。重要なのは、離散問題を近似するために連続確率分布を用いたランダム化アルゴリズムを深く掘り下げ、約e/(e-1)の期待競合比を実現することで、シンプルなアプローチよりも大幅に優れている点です。単一の意思決定においては現実世界では直接適用できませんが、このアルゴリズムは、多くの同様の選択を含むシナリオに対して、理論的に最適な戦略を提供します。