科学・技術

k-server 予想は真実である

The k-server conjecture is true (arxiv.org)

82 pointsby iamsyr2026年9月15日35 コメント

要約

この論文は、決定論的なオンラインアルゴリズムが任意の計量空間で競争比 k を達成できるとする k-server 予想を証明したことを発表しています。具体的には、ワーク関数アルゴリズムがこれを満たすことが示されています。証明は、ワーク関数を行列として代数的に表現し、最小値と加算操作を形式的な式の加算と乗算に対応させ、各ワーク関数値を行列の k 列の行列式に対応させることで行われます。

全文翻訳

コンピュータサイエンス > データ構造とアルゴリズム

arXiv:2609.15979 (cs)

[2026年9月14日提出]

タイトル: kサーバー予想は真である

著者: Christian Coester, Elias Koutsoupias, Marek Zbysiński

Christian Coesterと他の2名の著者による「kサーバー予想は真である」というタイトルの論文のPDFを表示

PDFを表示 HTML (実験的)

要旨: kサーバー予想は、決定論的なオンラインアルゴリズムが任意の距離空間において競争比kを達成できると述べている。我々は本予想を証明する。具体的には、ワークファンクションアルゴリズムがこれを満たすことを示す。我々の証明は、ワークファンクションの自然な代数的表現を、構成に至る全ての実行可能なパスを符号化する行列として用いる。この表現において、最適コストの定義に現れる最小化と加算の操作は、形式的な式の加算と乗算に対応し、各ワークファンクション値は行列のk列の行列式に対応する。リクエストの到着は、基底変換と行置換による表現の更新を引き起こす。償却解析は、元の行列表現の座標のペアからなるより大きな行列で定義されたポテンシャル関数に基づいている。


件名:	データ構造とアルゴリズム (cs.DS)
引用:	arXiv:2609.15979 [[cs.DS]]
	(またはこのバージョンについては arXiv:2609.15979v1 [[cs.DS]])
	https://doi.org/10.48550/arXiv.2609.15979 DataCite経由のarXiv発行DOI