pith. machine review for the scientific record. sign in

arxiv: 2605.10895 · v1 · submitted 2026-05-11 · 💻 cs.DS · cs.CG

Recognition: no theorem link

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

Anupam Gupta, Fabrizio Grandoni, Jatin Yadav

Pith reviewed 2026-05-12 03:57 UTC · model grok-4.3

classification 💻 cs.DS cs.CG
keywords FPT approximation schemesmin-sum radii clusteringmin-sum diameters clusteringmetric spacesparameterized algorithmsapproximation algorithmsclustering problems
0
0 comments X

The pith

FPT approximation schemes compute (1+ε)-approximations for min-sum radii and min-sum diameters clustering in time exponential only in k.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops approximation algorithms for min-sum radii and min-sum diameters clustering in metric spaces. Given any ε > 0, it produces clusterings whose total radius sum or diameter sum is at most (1+ε) times the optimum, with running time (1/ε)^k n^{O(1)} for diameters and (1/ε)^{O(k/ε log 1/ε)} n^{poly(1/ε)} for radii. These bounds improve on the prior best FPT approximations of 4+ε and 2+ε. A sympathetic reader would care because the schemes make near-optimal solutions feasible whenever the number of clusters k is moderate, settling an open question on whether FPT approximation schemes exist for these problems.

Core claim

We present FPT approximation schemes for both problems: given ε>0, (1+ε)-approximations for MSD and MSR can be computed in time (1/ε)^k n^{O(1)} and (1/ε)^{O(k/ε log 1/ε)} n^{poly(1/ε)} respectively, where the input is a metric space and k is the number of clusters.

What carries the argument

The FPT approximation scheme that controls the enumeration of candidate centers and partitions to achieve the (1+ε) guarantee while keeping the exponential dependence only on k (or k/ε).

If this is right

  • Both problems now admit approximation schemes with arbitrarily small error in FPT time.
  • The previous constant-factor FPT approximations are superseded for any fixed ε.
  • Near-optimal clusterings become computable in time polynomial in n whenever k is small.
  • The existence of these schemes resolves the open question of FPT-AS for min-sum radii and diameters.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same enumeration technique might extend to other sum-based clustering objectives such as min-sum k-means.
  • For moderate ε the milder exponential for diameters could be the more practical of the two schemes.
  • Combining the schemes with local search or sampling could produce heuristics that work for larger k.

Load-bearing premise

The input distances form a metric space satisfying the triangle inequality, and exponential dependence on k is permitted.

What would settle it

A metric-space instance with small k where every clustering returned by the scheme has sum of radii or diameters strictly larger than (1+ε) times the true optimum.

Figures

Figures reproduced from arXiv: 2605.10895 by Anupam Gupta, Fabrizio Grandoni, Jatin Yadav.

Figure 1
Figure 1. Figure 1: Projecting each point on the diameter (x, y). There are three clusters, blue, red and green. Each interval represents the range of distances from x for the points in the corresponding cluster. The algorithm chooses a random threshold R in [0, diam(S)] and splits the problem into left and right of the threshold. The created split is good if the threshold lies in the gap, that is, it does not lie on any of t… view at source ↗
Figure 2
Figure 2. Figure 2: Creation of a defensive ball Dj . The originally undefended optimal balls are given in orange. We start with an uncovered point cj . Since it is contained in the optimal ball B⋆ 1 , we start with Dj ← Ball(cj , 2r ⋆ 1 ), and mark B⋆ 1 as defended. Since B⋆ 2 ’s center c ⋆ 2 is inside Dj , we expand Dj by r ⋆ 2 to get Dj = Ball(cj , 2r ⋆ 1+r ⋆ 2 ) and mark B⋆ 2 as defended by Dj . Now B⋆ 3 , B⋆ 4 have their… view at source ↗
Figure 3
Figure 3. Figure 3: An example of the creation of subproblems. The left image describes the boundary balls before we [PITH_FULL_IMAGE:figures/full_fig_p020_3.png] view at source ↗
read the original 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)^kn^{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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 4 minor

Summary. The paper presents fixed-parameter tractable (FPT) approximation schemes for the Min-Sum Radii (MSR) and Min-Sum Diameters (MSD) clustering problems in general metric spaces. Given ε > 0 and parameter k (number of clusters), it computes (1+ε)-approximations for MSD in time (1/ε)^k n^{O(1)} and for MSR in time (1/ε)^{O(k/ε log 1/ε)} n^{poly(1/ε)}. These improve on prior FPT approximations with ratios 4+ε and 2+ε, respectively, and resolve open questions on the existence of FPT approximation schemes for both problems.

Significance. If the claimed running times and approximation guarantees hold, the results are significant for parameterized approximation algorithms. They establish the first FPT-AS (PTAS in k) for these min-sum clustering objectives under the metric assumption, with the MSD result having single-exponential dependence on k and the MSR result having a mildly super-exponential but still FPT dependence. The work provides concrete algorithmic constructions that advance the state of the art beyond constant-factor FPT approximations and may serve as a template for other clustering variants with sum-of-cost objectives.

minor comments (4)
  1. §2 (Preliminaries): the notation for the metric distance function d(·,·) and the definition of cluster radius vs. diameter should be stated explicitly with an equation to avoid ambiguity when the algorithms later refer to 'optimal radii'.
  2. §4 (MSD algorithm): the enumeration over candidate centers in the dynamic program could benefit from a short pseudocode block or a figure illustrating the recursion tree for small k, as the current prose description of the (1/ε)^k factor is dense.
  3. §6 (MSR algorithm): the dependence (1/ε)^{O(k/ε log 1/ε)} is derived from a combination of sampling and DP; a brief remark on whether the log 1/ε term can be removed (or why it is necessary) would strengthen the presentation.
  4. References: the citation list omits a few recent works on FPT clustering in metrics (e.g., on k-means with outliers); adding 2–3 targeted references would better situate the contribution.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of our paper, for recognizing the significance of the first FPT approximation schemes for Min-Sum Radii and Min-Sum Diameters clustering, and for recommending minor revision. The referee correctly notes that our algorithms improve upon the prior 4+ε and 2+ε FPT approximations and resolve the open questions on the existence of FPT-AS for these problems. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity in the derivation chain

full rationale

The paper presents new constructive FPT approximation schemes for the Min-Sum Radii and Min-Sum Diameters clustering problems in metric spaces. The central results are algorithmic: explicit running-time bounds of (1/ε)^k n^{O(1)} for MSD and (1/ε)^{O(k/ε log 1/ε)} n^{poly(1/ε)} for MSR that achieve (1+ε) approximation. These are derived from standard dynamic-programming and enumeration techniques over the parameter k, with no reduction of the claimed guarantees to fitted parameters, self-definitions, or load-bearing self-citations. The improvement over prior 4+ε and 2+ε FPT approximations is presented as the outcome of the new construction rather than a tautology. The derivation is therefore self-contained against the stated metric-space model and FPT parameterization.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work relies on standard properties of metric spaces and on the definition of FPT algorithms; no new entities or fitted constants are introduced in the abstract.

axioms (1)
  • domain assumption Input distances form a metric (satisfy triangle inequality).
    Standard assumption for the problem statements of MSR and MSD.

pith-pipeline@v0.9.0 · 5503 in / 1244 out tokens · 48996 ms · 2026-05-12T03:57:01.360140+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages

  1. [1]

    and Marathe, Madhav V

    Doddi, Srinivas R. and Marathe, Madhav V. and Ravi, S. S. and Taylor, David Scot and Widmayer, Peter. Approximation Algorithms for Clustering to Minimize the Sum of Diameters. Algorithm Theory - SWAT 2000. 2000

    work page 2000

  2. [2]

    2004 , note =

    Clustering to minimize the sum of cluster diameters , journal =. 2004 , note =. doi:https://doi.org/10.1016/j.jcss.2003.07.014 , url =

    work page doi:10.1016/j.jcss.2003.07.014 2004

  3. [3]

    Moritz Buchem and Katja Ettmayr and Hugo K. K. Rosado and Andreas Wiese , title =. Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , chapter =. 2024 , pages =. doi:10.1137/1.9781611977912.69 , URL =

    work page doi:10.1137/1.9781611977912.69 2024

  4. [4]

    and Varadarajan, Kasturi

    Gibson, Matt and Kanade, Gaurav and Krohn, Erik and Pirwani, Imran A. and Varadarajan, Kasturi. On Metric Clustering to Minimize the Sum of Radii. Algorithm Theory -- SWAT 2008. 2008

    work page 2008

  5. [5]

    Novel Properties of Hierarchical Probabilistic Partitions and Their Algorithmic Applications , year=

    Banerjee, Sandip and Bartal, Yair and Gottlieb, Lee-Ad and Hovav, Alon , booktitle=. Novel Properties of Hierarchical Probabilistic Partitions and Their Algorithmic Applications , year=

    work page

  6. [6]

    39th International Symposium on Computational Geometry (SoCG 2023) , pages =

    Bandyapadhyay, Sayan and Lochet, William and Saurabh, Saket , title =. 39th International Symposium on Computational Geometry (SoCG 2023) , pages =. 2023 , volume =. doi:10.4230/LIPIcs.SoCG.2023.12 , annote =

    work page doi:10.4230/lipics.socg.2023.12 2023

  7. [7]

    Chen, Xianrun and Xu, Dachuan and Xu, Yicheng and Zhang, Yong , title =. Proceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence and Thirty-Sixth Conference on Innovative Applications of Artificial Intelligence and Fourteenth Symposium on Educational Advances in Artificial Intelligence , articleno =. 2024 , isbn =. doi:10.1609/aaai.v38...

    work page doi:10.1609/aaai.v38i18.30053 2024

  8. [8]

    15th Innovations in Theoretical Computer Science Conference (ITCS 2024) , pages =

    Jaiswal, Ragesh and Kumar, Amit and Yadav, Jatin , title =. 15th Innovations in Theoretical Computer Science Conference (ITCS 2024) , pages =. 2024 , volume =. doi:10.4230/LIPIcs.ITCS.2024.65 , annote =

    work page doi:10.4230/lipics.itcs.2024.65 2024

  9. [9]

    28th Annual European Symposium on Algorithms (ESA 2020) , pages =

    Inamdar, Tanmay and Varadarajan, Kasturi , title =. 28th Annual European Symposium on Algorithms (ESA 2020) , pages =. 2020 , volume =. doi:10.4230/LIPIcs.ESA.2020.62 , annote =

    work page doi:10.4230/lipics.esa.2020.62 2020

  10. [10]

    2025 , eprint=

    FPT approximations for Capacitated Sum of Radii and Diameters , author=. 2025 , eprint=

    work page 2025

  11. [11]

    30th Annual European Symposium on Algorithms (ESA 2022) , pages =

    Friggstad, Zachary and Jamshidian, Mahya , title =. 30th Annual European Symposium on Algorithms (ESA 2022) , pages =. 2022 , volume =. doi:10.4230/LIPIcs.ESA.2022.56 , annote =

    work page doi:10.4230/lipics.esa.2022.56 2022

  12. [12]

    33rd Annual European Symposium on Algorithms (ESA 2025) , pages =

    Bagheri Nezhad, Sina and Bandyapadhyay, Sayan and Chen, Tianzhi , title =. 33rd Annual European Symposium on Algorithms (ESA 2025) , pages =. 2025 , volume =. doi:10.4230/LIPIcs.ESA.2025.62 , annote =

    work page doi:10.4230/lipics.esa.2025.62 2025

  13. [13]

    35th International Symposium on Algorithms and Computation (ISAAC 2024) , pages =

    Carta, Lena and Drexler, Lukas and Hennes, Annika and R\". 35th International Symposium on Algorithms and Computation (ISAAC 2024) , pages =. 2024 , volume =. doi:10.4230/LIPIcs.ISAAC.2024.16 , annote =

    work page doi:10.4230/lipics.isaac.2024.16 2024

  14. [14]

    Approximation, Randomization, and Combinatorial Optimization

    Bandyapadhyay, Sayan and Chen, Tianzhi , title =. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025) , pages =. 2025 , volume =. doi:10.4230/LIPIcs.APPROX/RANDOM.2025.23 , annote =

    work page doi:10.4230/lipics.approx/random.2025.23 2025

  15. [15]

    Banerjee, Sandip and Bartal, Yair and Gottlieb, Lee-Ad and Hovav, Alon , title =. Proceedings of the Thirty-Ninth AAAI Conference on Artificial Intelligence and Thirty-Seventh Conference on Innovative Applications of Artificial Intelligence and Fifteenth Symposium on Educational Advances in Artificial Intelligence , articleno =. 2025 , isbn =. doi:10.1609...

    work page doi:10.1609/aaai.v39i15.33699 2025

  16. [16]

    Algorithmica , number =

    On Minimum Sum of Radii and Diameters Clustering , url =. Algorithmica , number =. 2015 , bdsk-url-1 =. doi:10.1007/s00453-014-9907-3 , author=

    work page doi:10.1007/s00453-014-9907-3 2015

  17. [17]

    and Varadarajan, Kasturi , title =

    Gibson, Matt and Kanade, Gaurav and Krohn, Erik and Pirwani, Imran A. and Varadarajan, Kasturi , title =. SIAM Journal on Computing , volume =. 2012 , doi =. https://doi.org/10.1137/100798144 , abstract =

    work page doi:10.1137/100798144 2012

  18. [18]

    46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) , pages =

    Cohen-Addad, Vincent and Gupta, Anupam and Kumar, Amit and Lee, Euiwoong and Li, Jason , title =. 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) , pages =. 2019 , volume =. doi:10.4230/LIPIcs.ICALP.2019.42 , annote =

    work page doi:10.4230/lipics.icalp.2019.42 2019