Loading article…
コンピュータサイエンスでは、オンライン アルゴリズムはさまざまな敵対者モデルに対する競争力を測定します。決定論的アルゴリズムの場合、敵対者は適応型オフライン敵対者と同じです。ランダム化オンライン アルゴリズムの場合、競争力は使用される敵対者モデルによって異なります。
共通の敵
一般的な 3 つの敵は、無意識の敵、適応型オンラインの敵、適応型オフラインの敵です。
気づかない敵は弱い敵と呼ばれることもあります。この敵はアルゴリズムのコードを知っていますが、アルゴリズムのランダム化された結果を知ることはできません。
適応型オンライン敵対者は、中程度の敵対者と呼ばれることもあります。この敵対者は、アルゴリズムの決定を知る前に、独自の決定を下す必要があります。
適応型オフラインの敵は、強力な敵と呼ばれることもあります。この敵は、乱数ジェネレーターも含めてすべてを知っています。この敵は非常に強力なので、ランダム化は役に立ちません。
重要な結果
S. Ben-David、A. Borodin、R. Karp、G. Tardos、A. Wigdersonによれば、次のようになります。
- 適応型オフラインの敵に対して α 競合性のあるランダム化アルゴリズムが存在する場合、α 競合性のある決定論的アルゴリズムも存在します。
- G が任意の適応型オンライン敵対者に対する c 競合ランダム化アルゴリズムであり、任意の無意識敵対者に対するランダム化 d 競合アルゴリズムがある場合、G は任意の適応型オフライン敵対者に対するランダム化 (c * d) 競合アルゴリズムです。
参照
参考文献
- ボロディン、A. ; エルヤニブ、R. (1998)。オンライン計算と競合分析。ケンブリッジ大学出版局。ISBN 978-0-521-56392-5。
- S. Ben-David; A. Borodin; R. Karp ; G. Tardos; A. Wigderson. (1994). 「オンライン アルゴリズムにおけるランダム化の威力について」(PDF) . Algorithmica . 11 : 2–14. doi :10.1007/BF01294260.
外部リンク
- オンラインアルゴリズムに関する論文の参考文献