k-server 予想は真実である

コンピュータサイエンス > データ構造とアルゴリズム arXiv:2609.15979 (cs) [2026 年 9 月 14 日提出] タイトル: k-server 予想は真実である 著者: Christian Coester, Elias Koutsoupias, Marek Zbysiński Christian Coester および他の 2 名の著者による「k-server 予想は真実である」というタイトルの PDF を表示 PDF を表示 HTML (実験的) 概要: k-server 予想は、決定論的なオンラインアルゴリズムが任意の計量空間で競争比 k を達成できると述べています。私たちはこの予想を証明します。具体的には、ワーク関数アルゴリズムがこれを満たすことを示します。私たちの証明は、ワーク関数を、可能なすべての構成へのパスをエンコードする行列の自然な代数的表現を使用して行われます。この表現では、最適なコストの定義に現れる最小値と加算操作は、形式的な式の加算と乗算に対応し、各ワーク関数値は行列の k 列の行列式に対応します。リクエストの到着は、基底の変更と行の置換によって表現を変更します。償却分析は、元の行列表現の座標のペアで構成されるより大きな行列で定義されたポテンシャル関数に基づいています。 主題: データ構造とアルゴリズム (cs.DS) 引用形式: arXiv:2609.15979 [cs.DS] (またはこのバージョンについては arXiv:2609.15979v1 [cs.DS]) https://doi.org/10.48550/arXiv.2609.15979 詳細はこちらをご覧ください arXiv-発行 DOI (DataCite 経由、登録保留中) 提出履歴 送信者: Marek Zbysiński [メールを表示] [v1] 月曜日、2026 年 9 月 14 日 17:58:11 UTC (22 KB) 全文リンク: 論文にアクセス: Christian Coester および他の 2 名の著者による「k-server 予想は真実である」というタイトルの PDF を表示 PDF を表示 HTML (実験的) TeX ソース ライセンスを表示 現在の閲覧コンテキスト: cs.DS < 前 | 次 > 新着 | 最新 | 2026-09 次の形式で閲覧を変更: cs 参考文献と引用 NASA ADS Google Scholar Semantic Scholar BibTeX 引用 読み込み中... BibTeX 形式の引用 × 読み込み中... 提供元データ: ブックマーク 書誌ツール 書誌および引用ツール 書誌エクスプローラー 書誌エクスプローラーを切り替える (エクスプローラーとは?) 接続された論文 接続された論文を切り替える (接続された論文とは?) Litmaps Litmaps を切り替える (Litmaps とは?) scite.ai scite スマート引用を切り替える (スマート引用とは?) コード、データ、メディア この論文に関連するコード、データ、メディア alphaXiv alphaXiv を切り替える (alphaXiv とは?) コード検索ツール Papers の CatalyzeX コードファインダー (Papers の CatalyzeX とは?) DagsHub DagsHub を切り替える (DagsHub とは?) GotitPub Gotit.pub を切り替える (GotitPub とは?) Huggingface Hugging Face を切り替える (Huggingface とは?) ScienceCast ScienceCast を切り替える (ScienceCast とは?) デモ デモ Replicate Replicate を切り替える (Replicate とは?) Spaces Hugging Face Spaces を切り替える (Spaces とは?) Spaces TXYZ.AI を切り替える (TXYZ.AI とは?) 関連記事 レコメンダーおよび検索ツール 影響力のある花へのリンク 影響力のある花 (影響力のある花とは?) CORE レコメンダー CORE レコメンダーを切り替える (CORE レコメンダーとは?) 著者 会場 機関 トピック arXivLabs について arXivLabs: コミュニティ協力者との実験的なプロジェクト arXivLabs は、協力者が arXiv の新機能を直接ウェブサイト上で開発および共有できるフレームワークです。arXivLabs と協力する個人および組織は、オープンさ、コミュニティ、卓越性、ユーザーデータプライバシーという私たちの価値観を受け入れ、遵守しています。arXiv はこれらの価値観にコミットしており、それらを遵守するパートナーのみと協力します。コミュニティに価値をもたらすプロジェクトのアイデアがありますか？ arXivLabs について詳しく学ぶ。 この論文の著者は誰ですか？ MathJax を無効にする (MathJax とは?)