Connected k-Center and k-Diameter Clustering
Preprint
Abstract
Motivated by an application from geodesy, we introduce a novel clustering problem which is a $k$-center (or k-diameter) problem with 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$. We call the resulting problems the connected $k$-center problem and the connected $k$-diameter problem. We prove several results on the complexity and approximability of these problems. Our main result is an $O(\log^2{k})$-approximation algorithm for the connected $k$-center and the connected $k$-diameter problem. For Euclidean metrics and metrics with constant doubling dimension, the approximation factor of this algorithm improves to $O(1)$. We also consider the special cases that the connectivity graph is a line or a tree. For the line we give optimal polynomial-time algorithms and for the case that the connectivity graph is a tree, we either give an optimal polynomial-time algorithm or a $2$-approximation algorithm for all variants of our model. We complement our upper bounds by several lower bounds.
Keywords
All Related Versions
This publication has 21 references indexed in Scilit:
- Diversity-Aware k-median: Clustering with Fair Center Representation2021
- Faster Algorithms for the Constrained k-means ProblemTheory of Computing Systems, 2017
- Matroid and Knapsack Center ProblemsAlgorithmica, 2015
- Centrality of trees for capacitated $k$ k -centerMathematical Programming, 2015
- Clustering spatial data with a geographic constraint: exploring local searchKnowledge and Information Systems, 2011
- Clustering with Diversity2010
- Primal-dual approximation algorithms for integral flow and multicut in treesAlgorithmica, 1997
- Low diameter graph decompositionsCombinatorica, 1993
- When are NP-hard location problems easy?Annals of Operations Research, 1984
- Easy and hard bottleneck location problemsDiscrete Applied Mathematics, 1979