2024/09/08 by Filtser, Arnold, Gadekar, Ameet · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2409.04984
The Capacitated Sum of Radii problem involves partitioning a set of points P, where each point p∈ P has capacity Up, into k clusters that minimize the sum of cluster radii, such that the number of points in the cluster centered at point p is at most Up. We begin by showing that the problem is APX-hard, and that under gap-ETH there is no parameterized approximation scheme (FPT-AS). We then construct a ≈5.83-approximation algorithm in FPT time (improving a previous ≈7.61 approximation in FPT time). Our results also hold when the objective is a general monotone symmetric norm of radii. We also improve the approximation factors for the uniform capacity case, and for the closely related problem of Capacitated Sum of Diameters.