Incremental (k, z)-Clustering on Graphs

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 O(k m^1+o(1)+ k^1+1λ m), where λ 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 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.

Reproductions