Minimum sum-of-radii clustering solved exactly for any constant stability
Exact Sum-of-Radii Clustering under Any Constant Stability
Data Structures and Algorithms
Summary
Clustering groups data points based on distances, often by optimizing the shape or size of clusters. This paper studies a type of clustering called Minimum Sum-of-Radii (MSR), which aims to minimize the sum of cluster radii. The authors show that MSR can be solved exactly and efficiently when data distances meet a broad stability condition, improving on prior results that needed stronger assumptions. They also clarify that checking stability or verifying optimality under perturbations is computationally hard. This advances understanding of when clustering can be reliably and quickly found.
What this means in practice
- •For data engineers: Design exact clustering algorithms for stable datasets where distance measurements vary within a known constant range.
- •For network planners: Use stable distance models to efficiently determine optimal location groups minimizing maximum cluster radius under uncertain metrics.
A theory result. No direct application yet.
Authors
Shyam Ravichandran, Lev Reyzin
Abstract
We establish a separation between the stability thresholds of Minimum Sum-of-Radii (MSR) clustering and two closely related objectives. Known hardness results show that, on general metrics, exact recovery for Minimum Sum-of-Diameters and symmetric $k$-center is hard for every fixed $1<γ<2$, unless NP=RP. We show that MSR admits deterministic polynomial-time exact recovery for every fixed $γ>1$, extending Gao and Reyzin's result for $γ\ge2$. All three results use the same Bilu--Linial stability model: the optimal partition remains uniquely optimal when each pairwise distance is multiplied by any factor in $[1,γ]$, without requiring the perturbed distances to satisfy the triangle inequality. The number of clusters is part of the input. For $1<γ<2$, our algorithm runs in $n^{O((γ-1)^{-5})}$ time. The main structural insight is that a cheap merge in one part of the instance would allow a profitable split elsewhere under a suitable perturbation, contradicting stability. The resulting exchange inequality controls local cluster density, which gives linear growth and hence bounded treewidth in local interaction graphs. We use random partitions to obtain these regions, solve them by dynamic programming, and then derandomize the construction. For rational input and fixed rational $γ>1$, recognizing stability in this model is coNP-complete. Verifying that a supplied partition remains uniquely optimal under all allowed perturbations is coNP-complete for both arbitrary symmetric and metric perturbations.