Polynomial-Time Constant-Approximation for Fair Sum-of-Radii Clustering

Sina Bagheri Nezhad Sayan Bandyapadhyay Tianzhi Chen · 2025

Read Polynomial-Time Constant-Approximation for Fair Sum-of-Radii Clustering by Sina Bagheri Nezhad Sayan Bandyapadhyay Tianzhi Chen (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-2504-14683.txt.

Introduction

Sina Bagheri Nezhad and co-authors speed up fair clustering under a radius cost in a 2025 paper. Fair clustering keeps group shares balanced inside every cluster formed. One cost measure sums the radius of each cluster rather than capping the worst. A prior method was fast only when the cluster count stayed tiny.

Their new method runs in full polynomial time with a fixed error bound. That puts the radius cost beside simpler costs with the same guarantee. The result extends to any number of groups when balance must be exact. The authors report clearing several hurdles that made this cost harder.

Catalog record

CREATORSina Bagheri Nezhad Sayan Bandyapadhyay Tianzhi Chen
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE177 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-14683

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Polynomial-Time Constant-Approximation for Fair Sum-of-Radii Clustering Sina Bagheri Nezhad Sayan Bandyapadhyay Tianzhi Chen Abstract In a seminal work, Chierichetti et al. [ 22 ] introduced the ( t , k ) (t,k) -fair clustering problem: Given a set of red points and a set of blue points in a metric space, a clustering is called fair if the number of red points in each cluster is at most t t times and at least 1 / t 1/t times the number of blue points in that cluster. The goal is to compute a fair clustering with at most k k clusters that optimizes certain objective function. Considering this problem, they designed a polynomial-time O ⁡ ( 1 ) O(1) - and O ⁡ ( t ) O(t) -approximation for the k k -center and the k k -median objective, respectively. Recently, Carta et al. [ 17 ] studied this problem with the sum-of-radii objective and obtained a ( 6 + ϵ ) (6+\epsilon) -approximation with running time O ⁡ ( ( k ​ log 1 + ϵ ⁡ ( k / ϵ ) ) k ​ n O ⁡ ( 1 ) ) O((k\log_{1+\epsilon}(k/\epsilon))^{k}n^{O(1)}) , i.e., fixed-parameter tractable in k k . Here n n is the input size. In this work, we design the first polynomial-time O ⁡ ( 1 ) O(1) -approximation for ( t , k ) (t,k) -fair clustering with the sum-of-radii objective, improving the result of Carta et al. Our result places sum-of-radii in the same group of objectives as k k -center, that admit polynomial-time O ⁡ ( 1 ) O(1) -approximations. This result also implies a polynomial-time O ⁡ ( 1 ) O(1) -approximation for the Euclidean version of the problem, for which an f ⁡ ( k ) ⋅ n O ⁡ ( 1 ) f(k)\cdot n^{O(1)} -time ( 1 + ϵ ) (1+\epsilon) -approximation was known due to Drexler et al. [ 27 ] . Here f f is an exponential function of k k . We are also able to extend our result to any arbitrary ℓ ≥ 2 \ell\geq 2 number of colors when t = 1 t=1 . This matches known results for the k k -center and k k -median objectives in this case. The significant disparity of sum-of-radii compared to k k -center and k k -median presents several complex challenges, all of which we successfully overcome in our work. Our main contribution is a novel cluster-merging-based analysis technique for sum-of-radii that helps us achieve the constant-approximation bounds. 1 Introduction Given a set of points P in a metric space (\Omega,d) and an integer k>0 , the task of clustering is to find a partition X_{1},\ldots,X_{k} of P into k groups or clusters such that each group has similar points. The similarity of the clusters is typically modeled using an objective function which is to be minimized. In this work, we focus on the sum-of-radii objective, which is defined as the sum of the radii of k balls that contain the points of the respective k clusters. The sum-of-radii objective has a different flavor than center-based objectives, such as k -center, k -median, and k -means. In these objectives, k representative points (or cluster centers) are chosen, and the corresponding clusters are formed by assigning the points of P to their nearest centers. Such a partition is popularly known as the Voronoi partition. It is not hard to see that an optimal sum-of-radii clustering is not necessarily a Voronoi partition. The study of sum-of-radii was motivated by the idea that it could potentially reduce the so-called dissection effect that is observed in k -center type objectives. In k -center, the goal is to minimize the maximum distance between points and their cluster centers. Equivalently, we would like to compute k balls of the minimum possible same radius, that contain all the points. Consequently, the points in a ground truth cluster might be assigned to different clusters to minimize the k -center objective. Such an effect can be reduced by using the sum of radii objective instead, as here one can use clusters of varying radii. Sum-of-radii clustering is known to be NP-hard even in planar metrics and metrics of constant doubling dimension [ 33 ] . Consequently, it has received substantial attention from the approximation algorithms community. Charikar and Panigrahy [ 18 ] designed a Primal-Dual and Lagrangian relaxation-based 3.504-approximation algorithm that runs in polynomial time (poly-time). Recently, using similar techniques, Friggstad and Jamshidian [ 29 ] improved the approximation factor to 3.389. The best-known approximation factor for sum-of-radii in polynomial time is 3+\epsilon for any \epsilon>0 , due to Buchem et al. [ 16 ] . In stark contrast to the center-based clustering problems, sum-of-radii admits a QPTAS [ 33 ] , which is based on a randomized metric partitioning scheme. Additionally, the problem can be solved exactly in polynomial time in the Euclidean metric of constant dimension [ 34 ] , a unique trait that has not been observed in any other popular clustering problem. The algorithm is based on a separator theorem that guarantees the existence of a balanced separator that intersects at most a constant number of optimal balls. The problem also admits polynomial time exact algorithms in other restricted settings, such as when singleton clusters are not allowed [ 11 ] and the metric is unweighted [ 37 ] . We note that poly-time O(1) -approximations are known for all three center-based objectives [ 35 , 5 , 44 ] . In recent years, sum-of-radii clustering has also been studied with additional constraints. One such popular constraint is the capacity constraint, which puts restriction on the number of points that each cluster can contain. In a series of articles [ 40 , 9 , 41 , 28 ] , O(1) -approximation algorithms have been designed for capacitated sum-of-radii with running time fixed-parameter tractable (FPT) in k (i.e., f(k)\cdot n^{O(1)} for a function f of k ), culminating in an approximation factor of 3. Inamdar and Varadarajan [ 40 ] studied sum-of-radii with a matroid constraint where the set of centers of the balls must be an independent set of a matroid. They obtain an FPT 9-approximation for this problem. The approximation factor has recently been improved to 3 by Chen et al. [ 20 ] . Obtaining a polynomial-time O(1) -approximation for any of these constrained versions is an interesting open question. However, poly-time O(1) -approximations are known for sum-of-radii with lower bounds and with outliers [ 3 , 16 ] . Sum-of-radii has also been studied with fairness constraints, which is the main focus of our work. Clustering with fairness constraints or fair clustering stems from the idea that protected groups (defined based on a sensitive feature, e.g., gender) must be well-represented in each cluster. In recent years, fair clustering has received significant attention from researchers across several areas of computer science. In a seminal work, Chierichetti et al. [ 22 ] introduced the (t,k) -fair clustering problem. In this problem, we are given a set P_{1} of red points, a set P_{2} of blue points, that together contain n points, and an integer balance parameter t\geq 1 . A

Read the complete text