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}{\eta}} m)$$ where $\eta$ is an arbitrary fixed constant, $\eta$ is at least $1$.
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.
Blogger's Review: The proposed incremental $(k, z)$-clustering algorithm achieves efficient approximations under adversarial updates in dynamic graphs, particularly showcasing adaptability and effectiveness in handling edge insertions. By introducing the technique of bicriteria approximate solutions, the researchers offer new insights into the dynamic clustering problem in graph theory, which holds significant theoretical and practical implications.