2026-07-20T07:28:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25854 2026-06-23T12:59:38Z ddc:004 open_access

FPT Approximations for Capacitated Sum of Radii and Diameters Filtser, Arnold Gadekar, Ameet clustering sum of radii sum of diameter capacitated clustering fpt The Capacitated Sum of Radii problem involves partitioning a set of points P, where each point p ∈ P has capacity U_p, 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 U_p. 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Arnold Filtser and Ameet Gadekar 2026 Is Part Of LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2026.48 urn:nbn:de:0030-drops-258545 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.48 eng https://creativecommons.org/licenses/by/4.0/legalcode