k-server予想、40年ぶりに証明される
मूल शीर्षक: The k-server conjecture is true
यह क्यों महत्वपूर्ण है
オンラインアルゴリズム理論の30年来の未解決問題が解かれたことで、競合解析の理論的基盤が確立される。
2026年9月14日、Christian Coester、Elias Koutsoupias、Marek Zbysińskiの3名がarXivに論文を投稿し、計算機科学の未解決問題「k-server予想」を証明したと発表した。決定論的オンラインアルゴリズムがすべてのmetric空間で競合比kを達成できることが示された。
k-server予想とは、決定論的オンラインアルゴリズムがすべてのmetric空間においてk台のサーバーで競合比kを達成できるという命題で、1990年にManasse、McGeoch、Sleatorらによって提唱された30年以上にわたる未解決問題である。
今回の論文でCoesterらは、「work function algorithm（仕事関数アルゴリズム）」がこの予想を満たすことを証明した。このアルゴリズム自体は以前から有力候補とされていたが、その競合比の証明は長年できていなかった。
証明の核心は、work functionを行列として自然に代数表現する手法にある。この表現では、最適コスト計算に現れる最小演算と加算演算が、形式的な式の加算と乗算に対応し、各work function値は行列のk列の行列式として表される。リクエストの到着は基底変換と行置き換えによって表現が更新される仕組みだ。
償却解析には、元の行列表現の座標ペアを座標とする、より大きな行列で定義されたポテンシャル関数が用いられている。論文はarXiv:2609.15979として公開されており、PDFで22KBとコンパクトな構成だ。
Koutsoupiasはk-server予想の重要な研究者として知られており、今回の共著は長年の研究の集大成とも言える。理論計算機科学において競合解析の根幹をなすこの予想の解決は、オンラインアルゴリズム分野全体に大きな影響を与えるとみられる。