New Algorithms and Hardness Results for Connected Clustering
Preprint
Abstract
Connected clustering denotes a family of constrained clustering problems in which we are given a distance metric and an undirected connectivity graph $G$ that can be completely unrelated to the metric. The aim is to partition the $n$ vertices into a given number $k$ of clusters such that every cluster forms a connected subgraph of $G$ and a given clustering objective gets minimized. The constraint that the clusters are connected has applications in many different fields, like for example community detection and geodesy. So far, $k$-center and $k$-median have been studied in this setting. It has been shown that connected $k$-median is $Ω(n^{1- ε})$-hard to approximate which also carries over to the connected $k$-means problem, while for connected $k$-center it remained an open question whether one can find a constant approximation in polynomial time. We answer this question by providing an $Ω(\log^*(k))$-hardness result for the problem. Given these hardness results, we study the problems on graphs with bounded treewidth. We provide exact algorithms that run in polynomial time if the treewidth $w$ is a constant. Furthermore, we obtain constant approximation algorithms that run in FPT time with respect to the parameter $\max(w,k)$. Additionally, we consider the min-sum-radii (MSR) and min-sum-diameter (MSD) objective. We prove that on general graphs connected MSR can be approximated with an approximation factor of $(3 + ε)$ and connected MSD with an approximation factor of $(4 + ε)$. The latter also directly improves the best known approximation guarantee for unconstrained MSD from $(6 + ε)$ to $(4 + ε)$.
Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- Better Guarantees for $k$-Means and Euclidean $k$-Median by Primal-Dual AlgorithmsSIAM Journal on Computing, 2019
- On Minimum Sum of Radii and Diameters ClusteringAlgorithmica, 2014
- Improved Steiner tree algorithms for bounded treewidthJournal of Discrete Algorithms, 2012
- Clustering spatial data with a geographic constraint: exploring local searchKnowledge and Information Systems, 2011
- Achieving anonymity via clusteringACM Transactions on Algorithms, 2010
- A General Approach for Incremental Approximation and Hierarchical ClusteringSIAM Journal on Computing, 2010
- Asymmetric k-center is log * n -hard to approximate2004
- Clustering to minimize the maximum intercluster distanceTheoretical Computer Science, 1985
- Graph minors. III. Planar tree-widthJournal of Combinatorial Theory, Series B, 1984
- Easy and hard bottleneck location problemsDiscrete Applied Mathematics, 1979