k-server予想、30年越しに証明される

k-server予想とは、決定的オンラインアルゴリズムが任意の距離空間において競合比kを達成できるという命題で、1990年代から未解決のまま残っていた理論計算機科学の重要問題の一つだ。

今回、Oxford大学のChristian Coesterら3名が「work function algorithm」がこの予想を満たすことを証明した。証明の核心は、work functionを行列で代数的に表現するアプローチにある。この表現では、最適コストの定義に現れる最小値と加算の操作が、形式的な式の加算と乗算に対応し、各work function値は行列のk列の行列式として表現される。リクエスト到着時は基底変換と行の置き換えによって表現を更新し、ポテンシャル関数を用いた償却解析によって競合比kが成立することを示した。論文はPDF・HTMLともにarXivで公開中（arXiv:2609.15979）。