Sponsor
This work was supported by the National Science Foundation under Grant No. AF 2311397.
Published In
Leibniz International Proceedings in Informatics Lipics
Document Type
Article
Publication Date
9-15-2025
Subjects
Computer science, Information storage and retrieval systems
Abstract
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 ϵ ·log2 k ϵ )n 4 , i.e., fixed-parameter tractable in k for constant ϵ. Our result directly improves upon the FPT (6 + ϵ)-approximation by Carta et al. [10]. 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
Rights
Copyright (c) 2025 The Authors
This work is licensed under a Creative Commons Attribution 4.0 International License.
DOI
10.4230/LIPIcs.APPROX/RANDOM.2025.23
Persistent Identifier
https://archives.pdx.edu/ds/psu/44217
Citation Details
Bandyapadhyay, Sayan and Chen, Tainzhi, "Improved FPT Approximation for Sum of Radii Clustering with Mergeable Constraints" (2025). Computer Science Faculty Publications and Presentations. 388.
https://archives.pdx.edu/ds/psu/44217