摘要
给定一个加权无向图、聚类数 $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+\frac{1}{\eta}} m)$$ 其中 $\eta$ 为任意固定常数，$\eta$ 取值至少为 $1$。
我们的增量算法分为两个阶段。在第一阶段，我们维护一个大小为 $$\tilde{O}(k)$$ 的常数因子双标准近似解，整体更新时间为 $$m^{1+o(1)}$$ 适用于所有对抗性边插入。这个阶段是对 Mettu 和 Plaxton 的双标准近似算法 [Machine Learning 2004] 的复杂适应，针对增量图进行优化。我们的一项关键技术结果是，可以假设其算法中的半径是单调不减的，同时近似比保持不变，这一属性可能具有独立的研究价值。
在第二阶段，我们在由双标准近似解诱导的动态加权实例上维持一个常数因子近似的 $(k,z)$-聚类解。对于这个子问题，我们结合使用动态扳机算法和静态 $(k,z)$-聚类算法。
博主点评： 本文提出的增量 $(k, z)$-聚类算法在动态图的对抗性更新中实现了高效的近似解，尤其是对边插入的处理展现了良好的适应性和有效性。通过引入双标准近似解的技术，研究者们为图论中的动态聚类问题提供了新的思路，具有重要的理论和实际意义。