k-server予想が35年越しに証明される
原題: The k-server conjecture is true
なぜ重要か
オンラインアルゴリズム設計の理論的基盤が確立され、キャッシング・ネットワーク資源管理など実応用分野の理論保証が強化される。
Christian Coester、Elias Koutsoupias、Marek Zbysiński の3名は2026年9月14日、理論計算機科学における未解決問題「k-server予想」を証明したとする論文をarXivに投稿した。決定的オンラインアルゴリズムがあらゆる距離空間において競合比kを達成できることを示し、具体的にはwork function algorithmがこの条件を満たすことを証明した。
k-server予想は1988年にManasse、McGeoch、Sleatorらが提唱して以来、約35年間にわたり理論計算機科学の最重要未解決問題の一つとして知られてきた。命題の核心は「k台のサーバーを持つ決定的オンラインアルゴリズムは、最適なオフラインアルゴリズムに対して競合比kを達成できる」というものだ。競合比kとは、オンラインアルゴリズムのコストが最適解のk倍以内に収まることを意味する。
今回の証明でCoesterらが採用した手法は、work function（作業関数）を行列として代数的に表現するアプローチだ。この表現では、最適コストの定義に現れる最小演算と加算が、形式的な式の加算と乗算にそれぞれ対応する。さらに各work function値は、その行列のk列の行列式として表現される。
リクエストが到着するたびに、この行列表現は基底変換と行置換によって更新される。償却解析（amortized analysis）には、元の行列表現の座標のペアを座標とする、より大きな行列によって定義されるポテンシャル関数を用いた。
論文はPDFとHTML（実験的）形式でarXivから閲覧可能で、全22KBとコンパクトにまとめられている。査読を経た正式な学術誌への掲載はこれからだが、理論計算機科学コミュニティではすでに注目を集めている。著者の一人Elias Koutsoupiasは、k-server問題の研究で長年知られた第一人者であり、その当事者が証明に加わった点も話題となっている。