On the Parameterized Approximability of (Mergeable) Sum of Radii Clustering

Ameet Gadekar · 2026

Read On the Parameterized Approximability of (Mergeable) Sum of Radii Clustering by Ameet Gadekar (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-06398.txt.

Description

Ameet Gadekar studies the sum of radii clustering problem, which asks for k balls covering all points in a metric space while minimizing the sum of their radii. Despite much work on approximation and parameterized algorithms, its exact parameterized complexity and the chance of efficient schemes stayed open.

Gadekar shows the problem is W[2]-hard in k and rules out efficient parameterized approximation schemes unless a standard complexity collapse occurs. Stronger lower bounds follow from the Exponential Time Hypothesis. For mergeable constraints, covering fairness and diversity rules, a faster parameterized approximation improves the prior guarantee, with a better bound when an assignment subroutine is available.

Catalog record

CREATORAmeet Gadekar
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE66 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

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

Browse the full library · About the Tower of Babel