Graphs 上の (k, z) 分割のインкреメンタルアルゴリズム

arXiv:2602.08542v1 Announce Type: cross 要旨：重み付けされた非対称グラフ、クラスター数 k、および指数 z が与えられた場合、グラフ上の (k, z) 分割問題の目標は、各頂点とその最も近い中心への距離の z 乗の和を最小化するように、k 個の頂点を中心として選択することである。動的な設定では、グラフは敵対的なエッジ更新に曝され、誘導された最短距離度量における明示的な (k, z) 分割解を維持することが目標である。 効率的な動的 k-中心近似アルゴリズムはグラフ上で存在する [Cruciani et al. SODA 2024] に基づき、私の知る限り、動的な (k,z) 分割問題に対する同様の結果を提供する以前の作業は存在しない。この論文の主要な結果として、私たちは、エッジ挿入が進行するグラフにおいて、高確率で定数倍の近似率を維持するランダム化されたインкреメンタル (k, z) 分割アルゴリズムを開発した。全更新時間が $ ilde O(k m^{1+o(1)}+ k^{1+rac{1}{eta}} m)$ である ($eta eq 1$ は任意の固定定数)。私たちのインкреメンタルアルゴリズムは二つの段階で構成される。最初の段階では、全敵対的なエッジ挿入に対して $ ilde{O}(k)$ サイズの定数倍のビークリテリア近似解を維持する。この最初の段階は、Mettu と Plaxton [機械学習 2004] のビークリテリア近似アルゴリズムをインкреメンタルグラフに対して複雑に適応させたものである。私たちの主要な技術的結果の一つは、そのアルゴリズムの半径を非減少とみなしつつ、近似比が一定であることを仮定できるという点であり、これは独立した興味を持てる性質である。第二の段階では、ビークリテリア近似解によって誘導された動的な重み付けインスタンス上で、定数倍の近似率の (k,z) 分割解を維持する。このサブ問題については、動的なスパナーアルゴリズムと静的な (k,z) 分割アルゴリズムを採用した。

arXiv:2602.08542v1 Announce Type: cross Abstract: Given a weighted undirected graph, a number of clusters $k$, and an exponent $z$, the goal in the $(k, z)$-clustering problem on graphs is to select $k$ vertices as centers that minimize the sum of the distances raised to the power $z$ of each vertex to its closest center. In the dynamic setting, the graph is subject to adversarial edge updates, and the goal is to maintain explicitly an exact $(k, z)$-clustering solution in the induced shortest-path metric. While efficient dynamic $k$-center approximation algorithms on graphs exist [Cruciani et al. SODA 2024], to the best of our knowledge, no prior work provides similar results for the dynamic $(k,z)$-clustering problem. As the main result of this paper, we develop a randomized incremental $(k, z)$-clustering algorithm that maintains with high probability a constant-factor approximation in a graph undergoing edge insertions with a total update time of $\tilde O(k m^{1+o(1)}+ k^{1+\frac{1}{\lambda}} m)$, where $\lambda \geq 1$ is an arbitrary fixed constant. Our incremental algorithm consists of two stages. In the first stage, we maintain a constant-factor bicriteria approximate solution of size $\tilde{O}(k)$ with a total update time of $m^{1+o(1)}$ over all adversarial edge insertions. This first stage is an intricate adaptation of the bicriteria approximation algorithm by Mettu and Plaxton [Machine Learning 2004] to incremental graphs. One of our key technical results is that the radii in their algorithm can be assumed to be non-decreasing while the approximation ratio remains constant, a property that may be of independent interest. In the second stage, we maintain a constant-factor approximate $(k,z)$-clustering solution on a dynamic weighted instance induced by the bicriteria approximate solution. For this subproblem, we employ a dynamic spanner algorithm together with a static $(k,z)$-clustering algorithm.