Relax and Merge: A Simple Yet Effective Framework for Solving Fair k-Means and k-sparse Wasserstein Barycenter Problems
Abstract
The fairness of clustering algorithms has gained widespread attention across various areas in machine learning. In this paper, we study fair k-means clustering in Euclidean space. Given a dataset comprising several groups, the fairness constraint requires that each cluster should contain a proportion of points from each group within specified lower and upper bounds. Due to these fairness constraints, determining the locations of k centers and finding the induced partition are quite challenging tasks. We propose a novel "Relax and Merge" framework that returns a (1 + 4ρ + O(ϵ))-approximate solution, where ρ is the approximate ratio of an off-the-shelf vanilla k-means algorithm and O(ϵ) can be an arbitrarily small positive number. If equipped with a PTAS of k-means, our solution can achieve an approximation ratio of (5 + O(ϵ)) with only a slight violation of the fairness constraints, which improves the current state-of-the-art approximation guarantee. Furthermore, using our framework, we can also obtain a (1 + 4ρ + O(ϵ))-approximate solution for the k-sparse Wasserstein Barycenter problem, which is a fundamental optimization problem in the field of optimal transport, and a (2 + 6ρ)-approximate solution for the strictly fair k-means clustering with no violation, both of which are better than the current state-of-the-art methods. In addition, the empirical results demonstrate that our proposed algorithm can significantly outperform baseline approaches in terms of clustering cost.
The first two authors contribute equally. 1 In their paper, the approximate ratio is written as (2 + ρ) because they added a squared root to the k-means cost function.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
1 top-tier paper has cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
Cited by top-tier papers1
Builds on3
- Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast AlgorithmTianyi Lin, Nhat Ho, Xi Chen, Marco Cuturi et al.NeurIPS 2020 · 60 citations
- The Power of Uniform Sampling for CoresetsVladimir Braverman, Vincent Cohen-Addad, Shaofeng H.-C. Jiang, Robert Krauthgamer et al.FOCS 2022 · 20 citations
- Approximating Fair Clustering with Cascaded Norm ObjectivesEden Chlamtác, Yury Makarychev, Ali VakilianSODA 2022 · 15 citations
Related papers
- KFC: A Scalable Approximation Algorithm for -center Fair ClusteringElfarouk Harb, Ho Shan LamNeurIPS 2020 · 28 citations
- Approximate Group Fairness for ClusteringBo Li, Lijun Li, Ankang Sun, Chenhao Wang et al.ICML 2021 · 28 citations
- Fair Clustering via AlignmentKunwoong Kim, Jihu Lee, Sangchul Park, Yongdai KimICML 2025
- Fast and Accurate Fair k-Center Clustering in Doubling MetricsMatteo Ceccarello, Andrea Pietracaprina, Geppino PucciWWW 2024 · 10 citations
- Approximation Algorithms for Fair Range ClusteringSèdjro Salomon Hotegni, Sepideh Mahabadi, Ali VakilianICML 2023 · 25 citations
