Connected k-Center and k-Diameter Clustering

Abstract Motivated by an application from geodesy, we study the connected k-center problem and the connected k-diameter problem . The former problem has been introduced by Ge et al. (ACM Trans Knowl Discov Data 2(2):1–35, 2008. https://doi.org/10.1145/1376815.1376816 ) to model clustering of data sets with both attribute and relationship data. These problems arise from the classical k -center and k -diameter problems by adding a side constraint. For the side constraint, we are given an undirected connectivity graph G on the input points, and a clustering is now only feasible if every cluster induces a connected subgraph in G . Usually in clustering problems one assumes that the clusters are pairwise disjoint. We study this case but additionally also the case that clusters are allowed to be non-disjoint. This can help to satisfy the connectivity constraints. Our main result is an $$O(\log ^2k)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mo>log</mml:mo> <mml:mn>2</mml:mn> </mml:msup> <mml:mi>k</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> -approximation algorithm for the disjoint connected k -center and k -diameter problem. For Euclidean spaces of constant dimension and for metrics with constant doubling dimension, the approximation factor improves to O (1). Our algorithm works by computing a non-disjoint connected clustering first and transforming it into a disjoint connected clustering. We complement these upper bounds by several upper and lower bounds for variations and special cases of the model.