2026-07-23T19:07:48Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24389 2025-12-12T15:01:22Z ddc:004 open_access

Improved FPT Approximation for Sum of Radii Clustering with Mergeable Constraints Bandyapadhyay, Sayan Chen, Tianzhi sum-of-radii clustering mergeable constraints approximation algorithm In this work, we study k-min-sum-of-radii (k-MSR) clustering under mergeable constraints. k-MSR seeks to group data points using a set of up to k balls, such that the sum of the radii of the balls is minimized. A clustering constraint is called mergeable if merging two clusters satisfying the constraint, results in a cluster that also satisfies the constraint. Many popularly studied constraints are mergeable, including fairness constraints and lower bound constraints. In our work, we design a (4+ε)-approximation for k-MSR under any given mergeable constraint with runtime 2^{O(k/(ε)⋅log²k/ε)} n⁴, i.e., fixed-parameter tractable in k for constant ε. Our result directly improves upon the FPT (6+ε)-approximation by Carta et al. [Carta et al., 2024]. We also provide a hardness result that excludes the exact solvability of k-MSR under any given mergeable constraint in time f(k)n^o(k), assuming ETH is true. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sayan Bandyapadhyay and Tianzhi Chen 2025 Is Part Of LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2025.23 urn:nbn:de:0030-drops-243894 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.23 eng https://creativecommons.org/licenses/by/4.0/legalcode