2026-07-25T06:06:27Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24530 2025-12-16T14:00:25Z ddc:004 open_access

Polynomial-Time Constant-Approximation for Fair Sum-Of-Radii Clustering Bagheri Nezhad, Sina Bandyapadhyay, Sayan Chen, Tianzhi fair clustering sum-of-radii clustering approximation algorithms In a seminal work, Chierichetti et al. [Chierichetti et al., 2017] introduced the (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 times and at least 1/t times the number of blue points in that cluster. The goal is to compute a fair clustering with at most k clusters that optimizes certain objective function. Considering this problem, they designed a polynomial-time O(1)- and O(t)-approximation for the k-center and the k-median objective, respectively. Recently, Carta et al. [Carta et al., 2024] studied this problem with the sum-of-radii objective and obtained a (6+ε)-approximation with running time O((k log_{1+ε}(k/ε))^k n^O(1)), i.e., fixed-parameter tractable in k. Here n is the input size. In this work, we design the first polynomial-time O(1)-approximation for (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-center, that admit polynomial-time O(1)-approximations. This result also implies a polynomial-time O(1)-approximation for the Euclidean version of the problem, for which an f(k)⋅n^O(1)-time (1+ε)-approximation was known due to Drexler et al. [Drexler et al., 2023]. Here f is an exponential function of k. We are also able to extend our result to any arbitrary 𝓁 ≥ 2 number of colors when t = 1. This matches known results for the k-center and k-median objectives in this case. The significant disparity of sum-of-radii compared to k-center and 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sina Bagheri Nezhad and Sayan Bandyapadhyay and Tianzhi Chen 2025 Is Part Of LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2025.62 urn:nbn:de:0030-drops-245309 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.62 eng https://creativecommons.org/licenses/by/4.0/legalcode