k-server予想、35年越しに証明
원제: The k-server conjecture is true
왜 중요한가
オンラインアルゴリズム理論の基盤的未解決問題が解決されたことで、キャッシュ管理やルーティング最適化など実応用分野の理論的根拠が確立される。
2026年9月14日、Christian Coester、Elias Koutsoupias、Marek Zbysińskiの3名がarXivに論文を投稿し、計算機科学の未解決問題「k-server予想」を証明したと発表した。決定論的オンラインアルゴリズムが任意の距離空間において競合比kを達成可能であることを、Work Function Algorithmが満たすことを示す形で証明した。
k-server予想は1988年にManasse、McGeoch、Sleatorによって提唱された理論計算機科学の古典的難問。決定論的オンラインアルゴリズムが、k台のサーバーを使うあらゆる距離空間において、最適なオフラインアルゴリズムに対してk倍以内の競合比を達成できるという命題だ。約35年間、部分的な結果は積み上がってきたものの、完全な証明は誰も与えられていなかった。
今回の証明の核心は、Work Function（作業関数）アルゴリズムを行列の代数的表現として自然に捉え直した点にある。最適コストの定義に登場する「最小値」と「加算」の操作を、形式的な式の「加算」と「乗算」に対応させ、各作業関数の値を行列のk列の行列式として表現した。リクエストが到着するたびに、基底変換と行の置換によってこの表現を更新する。
償却解析には、元の行列表現の座標ペアを座標とする、より大きな行列から定義されたポテンシャル関数を用いた。この枠組みにより、これまで直接扱いが困難だった一般距離空間での解析を可能にしたという。
論文はarXiv（arXiv:2609.15979）に22KBのPDFとして公開されており、現時点では査読前の段階だが、理論計算機科学コミュニティで大きな注目を集めている。