Total: 1
We study the colorful sum of radii problem, where the input is a point set P partitioned into classes P1,P2,…,Pω, along with per-class outlier bounds m1,m2,…,mω, summing to m. The goal is to select a subset C⊆P of k centers and assign points to centers in C, allowing up to mi unassigned points (outliers) from each class Pi, while minimizing the sum of cluster radii. The radius of a cluster is defined as the maximum distance from any point in the cluster to its center. The classical (non-colorful) version of the sum of radii problem is known to be NP-hard, even on weighted planar graphs. The colorful sum of radii is introduced by Chekuri et al. (2022), who provide an O(logω)-approximation algorithm. In this paper, we present the first constant-factor approximation algorithms for the colorful sum of radii running in FPT (fixed-parameter tractable) time. Our contributions are twofold: We design an iterative covering algorithm that achieves a (2+ε)-approximation with running time exponential in both k and m; We further develop a (7+ε)-approximation algorithm by leveraging a colorful k-center subroutine, improving the running time by removing the exponential dependency on m.