オンラインアルゴリズム

オンラインアルゴリズムは、将来のリクエストに関する知識なしに、入力が到着するにつれて取り消し不能な決定を下す必要があります。その品質は、入力全体を事前に把握している最適なアルゴリズムとの比較分析によって測定されます。

Definition

オンラインアルゴリズムは、一連のリクエストとして入力を受け取り、将来のリクエストを見ることなく、それぞれに即座に取り消し不能な応答をしなければなりません。その競争率は、そのコストと、リクエストシーケンス全体を知っている最適なオフラインアルゴリズムのコストとの最悪ケースの比率です。

Scope

このトピックでは、入力を順次処理し、後の入力が判明する前に決定を確定するアルゴリズム、および最適なオフラインの敵対者に対してそれらを評価するために使用される競争率フレームワークについて説明します。これには、ページングとキャッシング、リスト更新、スキーレンタル問題、k-サーバー問題、オンラインスケジューリングとビンパッキングなどの古典的な問題、およびより弱い敵対者に対する競争率を改善する上でのランダム化の役割が含まれます。

Core questions

• 将来が不明な場合、オンラインアルゴリズムはどのように評価されますか？
• 競争率は何を測定し、オフラインの敵対者とは何ですか？
• ページングやスキーレンタルなどの古典的な問題は、オンラインのトレードオフをどのように示していますか？
• ランダム化は、無知な敵対者に対する競争力をどのように改善できますか？
• どのような下限が、任意のオンラインアルゴリズムの競争力を制限しますか？

Key concepts

• オンライン対オフライン
• 競争率
• オフラインの敵対者
• ページングとキャッシング
• リスト更新
• スキーレンタル問題
• k-サーバー問題
• ランダム化された競争力

Key theories

競争分析

競争分析は、オンラインアルゴリズムのコストと最適なオフラインアルゴリズムのコストとの最悪ケースの比率によってオンラインアルゴリズムを評価し、入力に関する仮定に依存するのではなく、任意の入力シーケンスに対して成り立つ保証を提供します。

無知な敵対者に対するランダム化

ランダム化されたオンラインアルゴリズムは、無知な敵対者に対して、任意の決定論的アルゴリズムよりも厳密に優れた競争率を達成できます。これは、敵対者がアルゴリズムのランダムな選択を知らずに入力を固定しなければならないためです。

Clinical relevance

オンラインアルゴリズムは、将来の知識なしにシステムがリアルタイムで行う決定をモデル化します。これには、オペレーティングシステムやCPUにおけるキャッシュおよびページ置換、データ構造の自己組織化、動的なリソース割り当てと負荷分散、クラウドコンピューティングにおけるレンタルまたは購入の決定などが含まれます。競争分析は、このようなリアクティブシステムに対して最悪ケースの保証を提供します。

History

競争分析は、1985年にSleatorとTarjanによって、リスト更新およびページング規則の研究を通じて導入され、オンラインアルゴリズムの評価を最適なオフラインソリューションとの比較を中心に再構築しました。このフレームワークは、1990年代にk-サーバー問題とランダム化オンラインアルゴリズムを通じて拡張され、BorodinとEl-Yanivの1998年のモノグラフで概説されています。

Key figures

• Daniel Sleator
• Robert Tarjan
• Allan Borodin
• Ran El-Yaniv

Seminal works

• sleator1985
• borodin1998
• cormen2009

Frequently asked questions

競争率とは何ですか？

これは、オンラインアルゴリズムのコストと、入力全体を事前に把握している最適なアルゴリズムのコストとの最悪ケースの比率です。2-競争的なアルゴリズムは、任意の入力シーケンスにおいて、可能な限り最良のオフラインコストの2倍を超えるコストがかかることはありません。

なぜランダム化はオンラインアルゴリズムに役立つのでしょうか？

アルゴリズムのランダムな選択を見ずに、入力を固定する無知な敵対者に対して、ランダム化は敵対者がアルゴリズムの動作に合わせて最悪のケースを調整するのを防ぎ、任意の決定論的アルゴリズムが達成できるよりも厳密に優れた競争率を可能にします。