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

Fabrizio Grandoni, Anupam Gupta, Jatin Yadav · 2026

Read FPT Approximation Schemes for Min-Sum Radii and Min-Sum Diameters Clustering by Fabrizio Grandoni, Anupam Gupta, Jatin Yadav (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-10895.txt.

Introduction

Fabrizio Grandoni, Anupam Gupta, and Jatin Yadav close two long-open problems in clustering, giving approximation schemes for min-sum radii and min-sum diameters. Both problems split points in a metric space into k groups while minimizing the total of group radii or diameters.

For any chosen accuracy, their algorithms return solutions within that margin of optimal, in time that grows reasonably with the accuracy parameter and polynomially with input size. Prior fixed-parameter methods stopped at factors of four and two, so exact schemes had stayed out of reach. Clustering researchers get the first schemes that can hug optimality as closely as desired.

Catalog record

CREATORFabrizio Grandoni, Anupam Gupta, Jatin Yadav
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE121932
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.10895

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

FPT Approximation Schemes for Min-Sum Radii and Min-Sum Diameters Clustering Fabrizio Grandoni, Anupam Gupta, Jatin Yadav Abstract In the classical Min-Sum Radii problem ( MSR ) we are given a set X X of n n points in a metric space and a positive integer k ∈ [ n ] k\in[n] . Our goal is to partition X X into k 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 k . Specifically, given ε > 0 \varepsilon>0 , we show how to compute ( 1 + ε ) (1+\varepsilon) -approximations for both MSD and MSR in time ( 1 / ε ) k ​ n O ⁡ ( 1 ) (1/\varepsilon)^{k}n^{O(1)} and ( 1 / ε ) O ⁡ ( k / ε ​ log ⁡ 1 / ε ) ​ n poly ⁡ ( 1 / ε ) (1/\varepsilon)^{O(k/\varepsilon\log 1/\varepsilon)}n^{\poly(1/\varepsilon)} respectively. The previous best FPT approximation algorithms for these problems have approximation factors 4 + ε 4+\varepsilon and 2 + ε 2+\varepsilon , respectively, and finding an FPT approximation scheme for both these problems had been outstanding open problems. 1 Introduction We consider two classical clustering objectives closely related to each other: min-sum radii and min-sum diameters , which seek to partition the points of a given metric space into k clusters, such that the sum of their radii or diameters is minimized. Both these problems have long been known to be NP-hard, but their approximability has been a source of much interest, as we detail below. In this work, we study these questions from the perspective of parameterized complexity , and ask: what can we do in time f(k)\poly(n) , where k is the number of clusters and n the size of the metric space? Formally, both the Min-Sum Radii and Min-Sum Diameters problems are defined on a (symmetric) metric space \mathcal{M}=(X,d) with X being a collection of n points . Given an integer k\in[n] denoting the target number of clusters, the goal in both problems is to partition the point set X into k sets (also called clusters ) S_{1},S_{2},\ldots,S_{k} . The difference between the two problems is in their objective functions: • The diameter of a cluster S is the maximum distance between any pair of points in S —i.e., \operatorname{diam}(S)=\max_{p,q\in S}d(p,q). In the Min-Sum Diameters ( MSD ) problem, the goal is to minimize \sum_{i\in[k]}\operatorname{diam}(S_{i}) . • The center (or the 1 -center) of a cluster S is a point p\in X minimizing \max_{q\in S}d(p,q) ; the latter quantity is called the radius of the cluster.In other words, \operatorname{rad}(S):=\min_{p\in X}\max_{q\in S}d(p,q). In the Min-Sum Radii ( MSR ) problem, the goal is to minimize \sum_{i\in[k]}\operatorname{rad}(S_{i}) . Both these problems are NP-hard [ 11 , 14 ] , and hence have been studied using the lens of approximation algorithms. Over a sequence of works giving polynomial-time approximation algorithms [ 11 , 8 , 13 , 6 ] , the approximation ratio for MSR has been improved to 3+\varepsilon ; since the two objectives are separated by a factor of at most 2 , this implies a (6+\varepsilon) -approximation for MSD as well, which is currently the best approximation factor known. The MSD problem does not admit a polynomial time algorithm with an approximation factor of better than 2 , unless P=NP [ 11 ] ; however, MSR admits a quasi-polynomial time approximation scheme (QPTAS) [ 14 ] , and hence a polynomial time approximation scheme (PTAS) is likely to exist. MSR and MSD are also well-studied in terms of parameterized approximation algorithms, where we allow the running time to depend super-polynomially in some parameter. For the natural parameter k , the best known results are a 2+\varepsilon (resp., 4+\varepsilon ) approximation for MSR (resp., MSD ) in FPT time f(k,\varepsilon)\cdot n^{g(\varepsilon)} for some computable functions f,g [ 2 , 9 ] . In this work, our focus is on FPT approximation schemes —i.e., (1+\varepsilon) -approximation algorithms running in time f(k,\varepsilon)\cdot n^{\poly(1/\varepsilon)} for some computable function f . The following natural question remains unresolved: do these two problems admit FPT Approximation Schemes? 1.1 Our Results The main results of our work answer the above question in the affirmative. For the MSR problem, which is known to be W[1] -hard [ 4 ] , we substantially improve upon the mentioned (2+\varepsilon) -approximation in FPT time [ 2 , 9 ] . Theorem 1.1 (Min-Sum Radii) . For any \varepsilon>0 , one can compute a (1+\varepsilon) -approximation for MSR in deterministic time (1/\varepsilon)^{O(\nicefrac{{k}}{{\varepsilon}}\ln\nicefrac{{1}}{{\varepsilon}})}n^{O(\nicefrac{{1}}{{\varepsilon^{3}}}\ln\nicefrac{{1}}{{\varepsilon}})} . We then turn our attention to the MSD problem. It is remarkable that essentially all previous approximation algorithms for this problem were obtained by losing a factor of 2 over the results for MSR . In other words, the best approximation factors were 6+\varepsilon and 4+\varepsilon in polynomial and FPT time respectively. We manage to break past this issue, and give a (1+\varepsilon) -approximation in FPT time: Theorem 1.2 (Min-Sum Diameters) . For any \varepsilon>0 , one can compute a 1+\varepsilon approximation for MSD in randomized time (O(1/\varepsilon))^{k}n^{O(1)} and in deterministic time (O(k/\varepsilon))^{k}n^{O(1)} . Note that such a result is not possible in polynomial time: an approximation of better than a factor of 2 would imply that P=NP [ 11 ] . Our approach also gives an exact algorithm with runtime n^{k+O(1)} (see Appendix C ), thereby improving the previous best runtime of n^{5k+O(1)} given by [ 4 ] . The same algorithm can also be utilized to give an FPT approximation scheme for the MSD problem (and thus a FPT (2+\varepsilon) -approximation algorithm for the MSR problem) with mergeable constraints . Here, we are given an upper bound k on the number of clusters and each cluster is required to satisfy some constraint. The constraint is such that, if two disjoint subsets of points satisfy the constraint, then so does their union. Carta et al. [ 7 ] show that fairness constraints like exact fairness and ratio balance , as well as non-fairness constraints such as lower bounds on cluster sizes, are mergeable. The previous best known result for mergeable constraints is an FPT (4+\varepsilon) -approximation for MSR (and an implied FPT (8+\varepsilon) -approximation for MSD ) [ 1 ] . Theorem 1.3 (Mergeable clustering) . For any \varepsilon>0 , one can compute a (1+\varepsilon) -approximation for MSD (and thus a (2+\varepsilon) -approximation for MSR ) under any mergeable constraint (that is verifiable in polynomial time) in randomized time (O(1/\varepsilon))^{k}n^{O(1)} and in deterministic time (O(k/\varepsilon))^{k}n^{O(1)} . 1.2 Our Techniques 1.2.1 The Algorithm for Min-Sum Diameters Our FPT approximation scheme for MSD is surprisingly clean, once viewed from the right perspective. To explain the guiding intuition, let us present a slight variant of our algorithm. We claim that the following algorithm has probability at least (\varepsilon/k)^{O(k)} of returning a 1+O(\varepsilon) approximate solution; therefore, an FPT randomized approximation scheme can be obtained by repeating it an FPT number of times. Our recursive algorithm gets in input a subset of points S\subseteq X

Read the complete text