FPT Constant Approximation Algorithms for Colorful Sum of Radii Journal: Nuclear Physics B This paper is dedicated to the memory of Professor Costas Iliopoulos. This research was supported by PIFI grant, Chinese Academy of Sciences President’s International Fellowship Initiative, Grant No.2025PG0005
Shuilian Liu, Gregory Z. Gutin, Yicheng Xu, Yong Zhang · 2025
Read FPT Constant Approximation Algorithms for Colorful Sum of Radii Journal: Nuclear Physics B This paper is dedicated to the memory of Professor Costas Iliopoulos. This research was supported by PIFI grant, Chinese Academy of Sciences President’s International Fellowship Initiative, Grant No.2025PG0005 by Shuilian Liu, Gregory Z. Gutin, Yicheng Xu, Yong Zhang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-13191.txt.
Introduction
Shuilian Liu and co-authors speed up colorful clustering with outliers in a 2025 paper. Points arrive painted in classes, and each class may skip some points. Centers must cover the rest while keeping total radius small. The plain version of the task is already known to be hard.
Prior methods lost accuracy as the class count grew. Two new algorithms hold a fixed error bound in special fast time. One loops over coverings with cost growing in two size measures. The other drops one of those costs with a worse error bound.
Catalog record
| CREATOR | Shuilian Liu, Gregory Z. Gutin, Yicheng Xu, Yong Zhang |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 34 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-13191
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
FPT Constant Approximation Algorithms for Colorful Sum of Radii Journal: Nuclear Physics B This paper is dedicated to the memory of Professor Costas Iliopoulos. This research was supported by PIFI grant, Chinese Academy of Sciences President’s International Fellowship Initiative, Grant No.2025PG0005. Shuilian Liu, Gregory Z. Gutin, Yicheng Xu, Yong Zhang Abstract We study the colorful sum of radii problem, where the input is a point set P P partitioned into classes P 1 , P 2 , … , P ω P_{1},P_{2},\dots,P_{\omega} , along with per-class outlier bounds m 1 , m 2 , … , m ω m_{1},m_{2},\dots,m_{\omega} , summing to m m . The goal is to select a subset 𝒞 ⊆ P \mathcal{C}\subseteq P of k k centers and assign points to centers in 𝒞 \mathcal{C} , allowing up to m i m_{i} unassigned points (outliers) from each class P i 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 ω ) 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 + ε ) (2+\varepsilon) -approximation with running time exponential in both k k and m m ; We further develop a ( 7 + ε ) (7+\varepsilon) -approximation algorithm by leveraging a colorful k k -center subroutine, improving the running time by removing the exponential dependency on m m . 1 Introduction Centroid-based k -clustering problems have been extensively studied in theoretical computer science, combinatorial optimization, and computational geometry. Given a set P of n nodes in an edge-weighted complete graph and an integer k (the weight of each edge is set to be the distance between its nodes), the task is to select a subset \mathcal{C}\subseteq P of k centers and assign each node to its nearest center, aiming to minimize a clustering cost function such as k -center, k -median, or k -means. The k -center problem seeks to minimize the maximum distance from any node to its assigned center (i.e., the maximum cluster radius), while the k -median problem minimizes the sum of distances from all nodes to their respective centers. A compromise objective is the sum of radii problem, which is also a sum-based objective, but minimizes the sum of the radii of the k clusters. This objective is often favorable to k -center, as it helps to avoid the so-called dissection effect [ 18 , 22 ] , a phenomenon in which spatially close points are assigned to different clusters. While previously less explored compared to classical clustering objectives, the sum of radii has become popular in recent years, especially in the design of approximation and FPT algorithms. The problem is known to be NP-hard even on weighted planar graphs and constant doubling dimension metrics, as shown by Gibson et al. [ 17 ] . For general metrics, they also provide a quasi-polynomial time (1+\varepsilon) -approximation. Using a primal-dual technique, Buchem et al. [ 5 ] obtain a (3+\varepsilon) -approximation, improving upon earlier results with approximation ratios of 3.504 [ 8 ] and 3.389 [ 14 ] . On the parameterized side, Chen et al. [ 10 ] first present an FPT (fixed-parameter tractable) 2-approximation algorithm for the sum of radii problem, by a radius profile guessing scheme. Similar FPT techniques have also been applied to capacitated variants of the problem [ 19 , 3 , 20 , 13 ] . In recent years, fair clustering has emerged as a promising research direction aimed at ensuring that clustering outcomes do not disproportionately neglect or overrepresent certain groups. A foundational contribution in this area is due to Chierichetti et al. [ 12 ] , who initiated the study of fairness in clustering by proposing the notion of balanced clustering, which enforces proportional representation of groups within each cluster. Following this milestone, fair clustering has rapidly evolved into a diverse field with multiple fairness definitions, including bounded representation fairness [ 4 ] , proportionally fair clustering [ 11 ] , and socially fair clustering [ 16 ] , and others. Research on fairness with respect to the sum of radii remains relatively recent. Carta et al. [ 6 ] present a (6+\varepsilon) -approximation algorithm for the fair sum of radii problem under balanced clustering. More recently, Nezhad et al. [ 23 ] develop a polynomial-time constant-factor approximation algorithm for this problem by leveraging a degree-constrained subgraph computation technique [ 15 ] . We focus on a related but distinct model known as colorful clustering, introduced by Bandyapadhyay et al. [ 3 ] . The input is a node set P=\bigcup_{i=1}^{\omega}P_{i} , an integer k , and a vector \bm{m}=(m_{1},\ldots,m_{\omega}) that bounds the number of outliers allowed per group. The goal is to select k centers and assign each node to a center or leave it as an outlier, with at most m_{i} outliers from each group P_{i} . When \omega=1 , the problem reduces to the classical outlier-robust clustering, originally introduced by Charikar et al. [ 7 ] . In addition, the outlier-robust variant of the sum of radii problem admits a 3-approximation algorithm [ 5 ] , which remains the best-known result for this objective. Unlike traditional outlier-robust clustering, which may completely exclude certain groups as outliers, colorful clustering imposes multi-outlier constraints on each group to prevent this phenomenon. This formulation has recently attracted significant interest, leading to a range of approximation algorithms for colorful clustering under different objectives. Bandyapadhyay et al. [ 3 ] show that the natural LP for colorful k -center has an unbounded integrality gap. They address this by constructing a simplified LP and exploiting properties of basic feasible solutions to design a 2-pseudo approximation algorithm. Jia et al. [ 21 ] design an ingenious rounding framework that builds on a 2-pseudo approximation algorithm. By carefully exploiting the structure of well-separated instances where optimal clusters are sufficiently distant, they convert the pseudo-solution into a true 3-approximation. Meanwhile, Anegg et al. [ 2 ] integrate polyhedral sparsity arguments, based on Bandyapadhyay et al. [ 3 ] , with dynamic programming in a round-or-cut framework, resulting in a 4-approximation. Agrawal et al. [ 1 ] utilize a coreset for the k -median with outliers to develop an FPT (1+2/e+\varepsilon) -approximation algorithm for the colorful k -median. For the colorful sum of radii, Chekuri et al. [ 9 ] use the primal-dual method to design an O(\log\omega) -approximation algorithm. Our contributions Recent advances in fixed-parameter tractable algorithms have shown their potential to overcome long-standing barriers in approximation algorithms. This work provides the first constant FPT approximation algorithms for the colorful sum of radii problem. We propose an iterative covering algorithm that achieves a (2+\varepsilon) -approximation with running time exponential in both k and the number of outliers m . It