Published In

Leibniz International Proceedings in Informatics Lipics

Document Type

Conference Proceeding

Publication Date

2025

Subjects

Computer science, Information storage and retrieval systems, Theory of computation -- Approximation algorithms analysis

Abstract

In a seminal work, Chierichetti et al. [20] 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. [15] studied this problem with the sum-of-radii objective and obtained a (6 + ϵ)-approximation with running time O((klog1+ϵ(k/ϵ))knO(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) · nO(1)-time (1 + ϵ)-approximation was known due to Drexler et al. [24]. 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.

Rights

© 2025 SinaBagheriNezhad, Sayan Bandyapadhyay, and Tianzhi Chen; licensed under Creative Commons License CC-BY 4.0

DOI

10.4230/LIPIcs.ESA.2025.62

Persistent Identifier

https://archives.pdx.edu/ds/psu/44227

Download

Share

COinS