計量タスクシステム

タスクシステムは、オンラインアルゴリズムの可能な構成の集合をモデル化するために使用される数学的オブジェクトです。これらは、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}}$州内で実行されています$sj$スケジュールの処理コストは ${\displaystyle \mathrm {cost} (\pi ,\sigma )=\sum _{i=1}^{l}d(\pi (i-1),\pi (i))+T_{i}(\pi (i)).}$

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

オンライン問題の場合、通常通り、メトリックタスクシステムのアルゴリズムを分析する最も一般的な方法は競合分析であり、オンラインアルゴリズムのパフォーマンスを最適なオフラインアルゴリズムのパフォーマンスと比較します。決定論的なオンラインアルゴリズムの場合、タイトな境界が存在します。${\displaystyle 2n-1}$ボロディンら（1992）による競争比率について。

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

様々な種類の制限付き指標に対して、多くの結果が得られています。

• 敵対者モデル
• 競合分析
• 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)「オンライン問題への応用を伴う距離空間のラムゼイ型定理」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: 複数の名前: 著者リスト (リンク)

• アラン・ボロディンとラン・エル・ヤニフ（1998年）。オンライン計算と競合分析ケンブリッジ大学出版局、123～ 149ページ。 
• Allan Borodin、Nati Linial、Michael Saks (1992) 「計測タスクシステムのための最適なオンラインアルゴリズム」 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). "ミラー降下と不公平な接着によるツリー上のメトリックタスクシステム". Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms . arXiv : 1807.04404 .