メトリックタスクシステム

タスク システムは、オンライン アルゴリズムの可能な構成のセットをモデル化するために使用される数学的オブジェクトです。これらは、さまざまなオンライン問題をモデル化するために、 Borodin、Linial、およびSaks (1992) によって導入されました。タスク システムは、一連の状態と状態変更コストを決定します。タスク システムは、各要求が状態に処理時間を割り当てるように、一連の要求を入力として取得します。タスク システムのオンライン アルゴリズムの目的は、状態に関するタスクの処理によって発生する全体的なコストと、状態変更コストによって発生するコストを最小限に抑えるスケジュールを作成することです。

状態を変更するためのコスト関数がメトリックである場合、タスク システムはメトリック タスク システム(MTS) です。これは最も一般的なタイプのタスク システムです。メトリック タスク システムは、ページング、リスト アクセス、k サーバー問題(有限空間内) などのオンライン問題を一般化します。

タスク システムとは、 が状態の集合でが距離関数であるペアです。 がメトリックである場合、はメトリック タスク システムです。タスク システムへの入力は、各 に対して、が 番目のタスクを処理するときに状態の処理コストを決定する非負のエントリのベクトルとなるシーケンスです。 ${\displaystyle (S,d)}$${\displaystyle S=\{s_{1},s_{2},\dotsc ,s_{n}\}}$${\displaystyle d:S\times S\rightarrow \mathbb {R} }$${\displaystyle d}$${\displaystyle (S,d)}$${\displaystyle \sigma =T_{1},T_{2},\dotsc ,T_{l}}$${\displaystyle i}$${\displaystyle T_{i}}$${\displaystyle n}$${\displaystyle n}$${\displaystyle i}$

タスクシステムのアルゴリズムは、状態の順序を決定するスケジュールを作成します。たとえば、は、番目のタスクが状態で実行されることを意味します。スケジュールの処理コストは、 ${\displaystyle \pi}$${\displaystyle \pi (i)=s_{j}}$${\displaystyle i}$${\displaystyle T_{i}}$${\displaystyle s_{j}}$${\displaystyle \mathrm {cost} (\pi ,\sigma )=\sum _{i=1}^{l}d(\pi (i-1),\pi (i))+T_{i}(\pi (i)).}$

アルゴリズムの目的は、コストが最小になるスケジュールを見つけることです。

オンライン問題の場合と同様に、メトリックタスクシステムのアルゴリズムを分析する最も一般的な方法は競合分析であり、オンラインアルゴリズムのパフォーマンスが最適なオフラインアルゴリズムのパフォーマンスと比較されます。決定論的なオンラインアルゴリズムの場合、 Borodin et al. (1992) により競合比に 厳しい制限があります。${\displaystyle 2n-1}$

ランダム化オンラインアルゴリズムの場合、競争比率は によって下限が制限され、 によって上限が制限されます。下限は Bartal ら (2006、2005) によるものです。上限は Fiat と Mendel (2003) の結果を改善した Bubeck、Cohen、Lee、Lee (2018) によるものです。 ${\displaystyle \Omega (\log n/\log \log n)}$${\displaystyle O\left((\log n)^{2}\right)}$

さまざまな種類の制限されたメトリックに対して多くの結果があります。

• 敵対者モデル
• 競合分析
• Kサーバーの問題
• オンラインアルゴリズム
• ページ置換アルゴリズム
• リアルタイムコンピューティング

• Yair Bartal、Avrim Blum、Carl Burch、Andrew Tomkins ( 1997)。「メトリックタスクシステムのための polylog(n) 競合アルゴリズム」。第 29 回 ACM コンピューティング理論シンポジウムの議事録。pp. 711–719。doi : 10.1145/258533.258667。

• Yair Bartal、Béla Bollobás 、Manor Mendel ( 2006)。 「オンライン問題への応用を含む計量空間のRamsey型定理」。Journal of Computer and System Sciences。72 ( 5): 890–921。arXiv : cs/0406028。doi :10.1016/j.jcss.2005.05.008。S2CID 1450455  。{{cite journal}}: CS1 maint: 複数の名前: 著者リスト (リンク)

• Yair Bartal、Nathan Linial、Manor Mendel、Assaf Naor (2005)。 「計量的ラムゼー型現象について」。Annals of Mathematics。162 ( 2): 643–709。arXiv : math /0406353。doi : 10.4007/annals.2005.162.643。{{cite journal}}: CS1 maint: 複数の名前: 著者リスト (リンク)

• Allan Borodin、Ran El-Yaniv (1998)。オンライン計算と競合分析。ケンブリッジ大学出版局。pp. 123–149。
• Allan Borodin、Nati Linial、Michael Saks (1992)。「韻律タスクシステムの ための最適なオンラインアルゴリズム」。Journal of the ACM。39 ( 4): 745–763。doi : 10.1145 /146585.146588。S2CID 18783826。{{cite journal}}: CS1 maint: 複数の名前: 著者リスト (リンク)

• Amos Fiat & Manor Mendel (2003). 「不公平な計量タスクシステムとアプリケーションのためのより優れたアルゴリズム」SIAM J. Comput . 32 (6): 1403–1422. arXiv : cs/0406034 . doi :10.1137/S0097539700376159.

• Bubeck, Sébastien; Cohen, Michael B.; R. Lee, James & Lee, Yin Tat (2019). 「ミラー降下法と不公平な接着による木上のメトリックタスクシステム」。第 30 回 ACM- SIAM離散アルゴリズムシンポジウムの議事録。arXiv : 1807.04404。