k-サーバー問題

コンピュータサイエンスにおける未解決の問題:

任意のメトリック空間における - サーバー問題を解決するための - 競争アルゴリズムはありますか?${\displaystyle k}$${\displaystyle k}$

(コンピュータサイエンスにおける未解決の問題)

kサーバー問題とは、オンラインアルゴリズムのカテゴリに属する ​​理論計算機科学の問題であり、競争分析理論の中心となる計量空間に関する 2 つの抽象問題のうちの 1 つです(もう 1 つは計量タスク システム)。この問題では、オンライン アルゴリズムが計量空間内の点として表されるk台のサーバーの集合の移動を制御し、同じく空間内の点の形で表される要求を処理する必要があります。各要求が到着すると、アルゴリズムは要求された点にどのサーバーを移動するかを決定する必要があります。アルゴリズムの目的は、すべてのサーバーが移動する合計距離を、要求のシーケンス全体を事前に知っている最適な敵対者がサーバーを移動できた合計距離と比較して小さく保つことです。

この問題は、Mark Manasse、Lyle A. McGeoch、 Daniel Sleator (1988)によって初めて提起されました。 ^[1] kサーバー問題に関する最も顕著な未解決問題は、Manasse らによって提起されたいわゆる k サーバー予想です。この予想は、任意のメトリック空間で、サーバーの数kが任意で、競争率がちょうどkであるkサーバー問題を解くアルゴリズムが存在するというものです。Manasse らは、 k = 2 のとき、およびk +1 個の点を持つように制限されたいくつかのメトリック空間に対するより一般的なkの値のとき、この予想を証明できました。ChrobakとLarmore (1991)は、ツリー メトリックについてこの予想を証明しました。すべての距離が等しいメトリックの特殊なケースは、メモリ キャッシュ内のページ置換アルゴリズムの問​​題をモデル化するため、ページング問題と呼ばれ、 k競合アルゴリズムがあることも既に知られていました( SleatorとTarjan 1985)。Fiat ら(1990) は、任意の定数kと任意のメトリック空間に対して有限の競争比を持つアルゴリズムが存在することを最初に証明し、最後に Koutsoupias とPapadimitriou (1995) は、仕事関数アルゴリズム (WFA) の競争比が 2 k - 1 であることを証明しました。しかし、他の多くの研究者の努力にもかかわらず、競争比をkに下げること、または改善された下限を提供することは、2014 年現在も未解決のままです。最も一般的に信じられているシナリオは、仕事関数アルゴリズムがk競争的であるというものです。この方向で、2000 年に Bartal と Koutsoupias は、これがいくつかの特殊なケース (メトリック空間が直線、重み付きスター、またはk +2 ポイントの任意のメトリックである場合) に当てはまることを示しました。 ^{[アップデート]}

kサーバー予想にはランダム化アルゴリズムのバージョンもあり、任意の距離空間（少なくともk + 1個の点を持つ）で競争比O(log k )のランダム化アルゴリズムが存在するかどうかを問うものです。 ^[2] 2011年には、競争上界Õ(log ² k log ³ n)のランダム化アルゴリズムが見つかりました。^{[3] [4] 2017年には、競争上界O(log 6} k)のランダム化アルゴリズムが発表されましたが、^[5]後に撤回されました。^[6] 2022年には、この予想のランダム化バージョンが誤りであることが示されました。^{[2] [7] [8]}

問題をより具体的にするために、機器に問題がある場合、顧客サポート技術者を顧客のもとへ派遣することを想像してください。この例の問題では、メアリーとノアという 2 人の技術者が、カリフォルニア州サンフランシスコ、ワシントン DC、メリーランド州ボルチモアの 3 人の顧客にサービスを提供しています。k サーバー問題の場合、サーバーは技術者であるため、k = 2 となり、これは 2 サーバー問題です。ワシントンとボルチモアは 35 マイル (56 km) 離れていますが、サンフランシスコはどちらからも 3,000 マイル (4,800 km) 離れており、最初はメアリーとノアは両方ともサンフランシスコにいます。

リクエストにサーバーを割り当てるアルゴリズムを考えてみましょう。このアルゴリズムでは、リクエストに最も近いサーバーが常に割り当てられます。平日の午前中はワシントンの顧客がサポートを必要とし、平日の午後はボルチモアの顧客がサポートを必要とし、サンフランシスコの顧客はサポートを必要としないとします。次に、アルゴリズムはサーバーの 1 つ (たとえば Mary) をワシントン地域に割り当てます。その後、このサーバーは常に最も近いサーバーとなり、すべての顧客リクエストに割り当てられます。したがって、アルゴリズムでは毎日、ワシントンとボルチモアの間を往復する 70 マイル (110 km) の移動コストが発生します。このリクエスト パターンが 1 年間続くと、アルゴリズムは 20,500 マイル (33,000 km) の移動コストが発生します。3,000 マイルは Mary を東海岸に送るのに、17,500 マイルはワシントンとボルチモア間の移動にかかります。一方、将来のリクエスト スケジュールを知っている最適な敵対者は、メアリーとノアの両方をそれぞれワシントンとボルチモアに送り、6,000 マイル (9,700 km) の移動を一度支払うだけで、将来の移動コストを回避することができます。この入力に対するアルゴリズムの競争率は 20,500/6,000 つまり約 3.4 であり、この例のパラメーターを調整することで、このアルゴリズムの競争率は任意の大きさにすることができます。

したがって、常に最も近いサーバーを割り当てることは、最適とは程遠いことがわかります。一方、将来のリクエストを知らないアルゴリズムが技術者 2 人をサンフランシスコから遠ざけるのは愚かな行為に思えます。次のリクエストはサンフランシスコで発生する可能性があり、その場合はすぐに誰かを戻さなければならないからです。したがって、kサーバー アルゴリズムが敵に対して優れたパフォーマンスを発揮することは困難または不可能であると思われます。ただし、2 サーバーの問題については、合計移動距離が常に敵の距離の 2 倍以下になるアルゴリズムが存在します。kサーバー予想では、技術者の数が多い問題に対しても同様のソリューションが存在するとされています。

• Chrobak, Marek ; Larmore, Lawrence L. (1991). 「木上のKサーバーに最適なオンライン アルゴリズム」SIAM Journal on Computing . 20 (1): 144–148. CiteSeerX  10.1.1.53.2395 . doi :10.1137/0220008.

• Fiat, A.; Rabani, Y.; Ravid, Y. (1990) 「競合的kサーバー アルゴリズム」第 31 回 IEEE コンピュータ サイエンスの基礎に関するシンポジウムの議事録。 pp. 454–463。

• Koutsoupias, Elias; Papadimitriou, Christos H. (1995). 「 k-サーバー予想について」Journal of the ACM . 42 (5): 971–983. doi :10.1145/210118.210128. S2CID  5813837.

• マナッセ、マーク、マクギオック、ライル A.、スレイター、ダニエル D. (1990)。「サーバー問題に対する競合アルゴリズム」。アルゴリズムジャーナル。11 (2): 208–230。doi :10.1016/0196-6774(90)90003-W。

• Sleator, Daniel D. ; Tarjan, Robert E. (1985). 「リスト更新とページングルールの償却効率」Communications of the ACM . 28 (2): 202–208. doi : 10.1145/2786.2793 . S2CID  2494305.