FPT Constant Approximation Algorithms for Colorful Sum of Radii

We study the colorful sum of radii problem, where the input is a point set $P$ partitioned into classes $P_1,P_2,\dots ,P_{\omega }$, along with per-class outlier bounds $m_1,m_2,\dots ,m_{\omega }$, summing to $m$. The goal is to select a subset $\mathcal{C}\subseteq P$ of $k$ centers and assign points to centers in $\mathcal{C}$, allowing up to $m_i$ unassigned points (outliers) from each class $P_i$, 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 \omega )$-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+\epsilon )$-approximation with running time exponential in both $k$ and $m$; We further develop a $(7+\epsilon )$-approximation algorithm by leveraging a colorful $k$-center subroutine, improving the running time by removing the exponential dependency on $m$.