动态图上高效维护近似聚类解，支持边插入更新。
Incremental (k, z)-Clustering on Graphs
- 分两阶段增量维护聚类：先构造近似解，再优化聚类质量。
- 总更新时间复杂度为 $\tilde O(k m^{1+o(1)} + k^{1+1/λ} m)$，保持常数近似比。
- 适用于需要实时响应图结构变化的聚类场景，如社交网络分析。
给定一个带权无向图、聚类数 $k$ 与指数 $z$，$(k, z)$-聚类问题的目标是选择 $k$ 个顶点作为中心，最小化每个顶点到其最近中心距离的 $z$ 次幂之和。在动态设置下，图经历对抗性边插入，目标是在诱导的最短路径度量中显式维护精确的 $(k, z)$-聚类解。尽管已有高效动态 $k$-中心近似算法 [Cruciani et al. SODA 2024]，但此前尚无针对动态 $(k,z)$-聚类问题的类似结果。本文提出一种随机增量式 $(k, z)$-聚类算法，在边插入的动态图中以高概率维持常数因子近似解，总更新时间为 $\tilde O(k m^{1+o(1)} + k^{1+1/λ} m)$，其中 $λ \geq 1$ 为任意固定常数。算法分为两阶段：第一阶段维护大小为 $\tilde{O}(k)$ 的常数因子双准则近似解，总更新时间 $m^{1+o(1)}$；第二阶段基于该近似解构造动态加权实例，并结合动态展子图算法与静态 $(k,z)$-聚类算法维持最终解。
原文摘要 · Abstract (English)
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}λ} m)$, where $λ\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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。