FPT Approximation Schemes for Min-Sum Radii and Min-Sum Diameters Clustering
For theoretical computer scientists working on clustering, this resolves long-standing open problems by providing optimal approximation guarantees in FPT time.
The paper presents the first FPT approximation schemes for Min-Sum Radii and Min-Sum Diameters clustering, achieving (1+ε)-approximation in time exponential only in k and polynomial in n, solving open problems that previously had only constant-factor approximations.
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.