FPT Approximation Schemes for Min-Sum Radii and Min-Sum Diameters Clustering

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 $\epsilon >0$, we show how to compute $(1+\epsilon )$-approximations for both MSD and MSR in time $(1/\epsilon {)}^k{n}^{O(1)}$ and $(1/\epsilon {)}^{O(k/\epsilon \log 1/\epsilon )}{n}^{poly(1/\epsilon )}$ respectively. The previous best FPT approximation algorithms for these problems have approximation factors $4+\epsilon$ and $2+\epsilon$, respectively, and finding an FPT approximation scheme for both these problems had been outstanding open problems.