FPT Constant Approximation Algorithms for Colorful Sum of Radii

2025/06/16 by Shuilian Liu, Liu, Shuilian, Gregory Gutin +5
Computer Science · Mathematics · #Advanced Optimization Algorithms Research #Approximation Theory and Sequence Spaces #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Matrix Theory and Algorithms

paper · pdf · doi:10.48550/arxiv.2506.13191

openalex publication_date 2025/06/16 · openalex created_date 2025/10/13 · openalex updated_date 2026/07/28

Abstract

We study the colorful sum of radii problem, where the input is a point set P partitioned into classes P₁, P₂, …, P_ω, along with per-class outlier bounds m₁, m₂, …, 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. 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.

Citations

• Polynomial-Time Constant-Approximation for Fair Sum-of-Radii Clustering
• FPT Approximations for Fair k-Min-Sum-Radii
• FPT approximations for Capacitated Sum of Radii and Diameters
• FPT Approximation for Capacitated Sum of Radii
• Clustering What Matters: Optimal Approximation for Clustering with Outliers
• A Technique for Obtaining True Approximations for k-Center with\n Covering Constraints
• A Constant Approximation for Colorful k-Center
• Fair Algorithms for Clustering
• A (3+ε)-approximation algorithm for the minimum sum of radii problem with outliers and extensions for generalized lower bounds

Related

• FPT approximations for Capacitated Sum of Radii and Diameters
• Polynomial-Time Constant-Approximation for Fair Sum-of-Radii Clustering
• A (3+ε)-approximation algorithm for the minimum sum of radii problem with outliers and extensions for generalized lower bounds
• FPT Approximation for Capacitated Sum of Radii
• FPT Constant-Approximations for Capacitated Clustering to Minimize the Sum of Cluster Radii