オンラインアルゴリズム - スキーレンタル

Question

私はスキーレンタルのようなオンラインアルゴリズムを解決しようとしていますが、問題は少し異なります。

問題は私がN箱を持っていることであり、各箱にはX < M < Yと異なる箱に異なっていてもよいMコインがあります。私は1つの箱を選んで硬貨の数を確認することができます。この箱を選択するかスキップしてください（スキップしてもこの箱に戻れません）。

私の目的は、コインの数を最大にするように1つのボックスを選択することです。

私のアルゴリズムでは、パラメータGを選択して最初のボックスを開き、コインの数がGより大きい場合はそのボックスを選択し、いずれも選択しなかった場合は最後のものを選択します。あなたはNボックスを知っている場合は、あなたが最初のN/Eボックスをチェックすることができ、オフライン溶液に対して

Answer 1

を競争力の比を最適化するために、Gがどうあるべきか

（2.7 = E ...）、および最大ボックスを追跡（すべてをスキップして最大値にする）G =最大サイズ.Gより大きい最初のボックスを選択するか、最後にボックスを選択しない。

Chrisさんが彼のコメントで述べたように、これはSecretary Problemです。私が提供している方法は、この問題の最適な解決策です。詳細はリンクで見ることができますが、わかりません。 Gは？入力分布といくつかの追加情報に依存します。

Answer 2

定数Gを設定した場合、データを知っている敵がデータを準備していると仮定しなければなりません。彼らはあなたにそれを選択させるボックスを与えて、最後のボックスにYを含めるようにして、オフラインアルゴリズムY/G倍をより有益にします。 OTOHの場合、彼らはあなたにそれを拒否させるボックスを手に入れ、最後のボックスにXを入れるようにして、オフラインアルゴリズムG/X時間をより有益にします。最も悪いGはsqrt（XY）のように見えます。この場合、オフラインアルゴリズムは、より収益性の高いsqrt（Y/X）倍です。

ボックスを受け取る前にGをランダムに選択するオプションがありますか？その場合、あなたの敵はその配布のみを知っていますか？ X = 1の単純な例の有望な振る舞いに基づいて、ln Xとln Yの間でランダムにln Gを選択しますが、おそらくこの場合にはより良い解決策があります。それらを見つける1つの方法は、離散値のみを考慮することです。これはおそらくこの例の実際の場合です。そして、状況をあなたとあなたの敵の間のゼロサムゲームとみなします。