Constant FPT Approximation Algorithms for Colorful Sum of Radii

• Constant FPT Approximation Algorithms for Clustering • Colorful Sum of Radii with outliers • From an algorithm for Colorful k-center to one 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 , ⋯ , P ω , along with per-class outlier bounds m 1 , m 2 , ⋯ , 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 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. In this paper, we present the first constant-factor approximation algorithms for the colorful sum of radii running in 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 , where ϵ > 0 is an arbitrary constant; we further develop a ( 7 + ε ) -approximation algorithm running in time exponential only in k by leveraging a colorful k -center subroutine.