2024/05/16 by Sayan Bandyapadhyay, Bandyapadhyay, Sayan, Eden Chlamtáč +5 · 1 citation
Computer Science · #Advanced Clustering Algorithms Research #Artificial Intelligence (cs.AI) #Bayesian Methods and Mixture Models #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG)
paper · pdf · doi:10.48550/arxiv.2405.10378
openalex publication_date 2024/05/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this work, we study pairwise fair clustering with ℓ ≥ 2 groups, where for every cluster C and every group i ∈ [ℓ], the number of points in C from group i must be at most t times the number of points in C from any other group j ∈ [ℓ], for a given integer t. To the best of our knowledge, only bi-criteria approximation and exponential-time algorithms follow for this problem from the prior work on fair clustering problems when ℓ > 2. In our work, focusing on the ℓ > 2 case, we design the first polynomial-time O(k2⋅ ℓ ⋅ t)-approximation for this problem with k-median cost that does not violate the fairness constraints. We complement our algorithmic result by providing hardness of approximation results, which show that our problem even when ℓ=2 is almost as hard as the popular uniform capacitated k-median, for which no polynomial-time algorithm with an approximation factor of o(log k) is known.