FPT Approximation Schemes for Min-Sum Radii and Min-Sum Diameters Clustering
2026-05-11 • Data Structures and Algorithms
Data Structures and AlgorithmsComputational Geometry
AI summaryⓘ
The authors study two clustering problems where the goal is to divide a set of points into groups to minimize either the sum of cluster radii or diameters. They focus on approximation algorithms that run efficiently when the number of clusters, k, is fixed. Their main achievement is designing algorithms that get very close (within any small error ε) to the best possible solution for both problems, improving on prior algorithms with looser guarantees. This solves a long-standing open problem in the field of fixed-parameter tractable (FPT) approximation algorithms for these clustering tasks.
Min-Sum Radii (MSR)Min-Sum Diameters (MSD)clusteringmetric spaceradiusdiameterapproximation algorithmfixed-parameter tractability (FPT)FPT approximation schemeparameterized complexity
Authors
Fabrizio Grandoni, Anupam Gupta, Jatin Yadav
Abstract
In the classical Min-Sum Radii problem (MSR) we are given a set $X$ of $n$ points in a metric space and a positive integer $k\in [n]$. Our goal is to partition $X$ into $k$ subsets (the clusters) so as to minimize the sum of the radii of these clusters. The Min-Sum Diameters problem (MSD) is defined analogously, where instead of the radii of the clusters we consider their diameters. For both problems we present FPT approximation schemes for the natural parameter $k$. Specifically, given $ε>0$, we show how to compute $(1+ε)$-approximations for both MSD and MSR in time $(1/ε)^kn^{O(1)}$ and $(1/ε)^{O(k/ε\log 1/ε)}n^{poly(1/ε)}$ respectively. The previous best FPT approximation algorithms for these problems have approximation factors $4+ε$ and $2+ε$, respectively, and finding an FPT approximation scheme for both these problems had been outstanding open problems.