# Relax and Merge: A Simple Yet Effective Framework for Solving Fair k-Means and k-sparse Wasserstein Barycenter Problems

arXiv: https://arxiv.org/abs/2411.01115 · HTML: https://mlsanity.com/paper/2411.01115/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 58 references that are in the map.
- First posted on arXiv 2 Nov 2024.

## Builds on (most cited first, 22 of 22)

- [Fast Computation of Wasserstein Barycenters](https://mlsanity.com/paper/1310.4375/) (2013)
- [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018)
- [Fair Algorithms for Clustering](https://mlsanity.com/paper/1901.02393/) (2019)
- [Proportionally Fair Clustering](https://mlsanity.com/paper/1905.03674/) (2019)
- [Coresets for Clustering with Fairness Constraints](https://mlsanity.com/paper/1906.08484/) (2019)
- [On the cost of essentially fair clusterings](https://mlsanity.com/paper/1811.10319/) (2018)
- [A Smoothed Dual Approach for Variational Wasserstein Problems](https://mlsanity.com/paper/1503.02533/) (2015)
- [Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast Algorithm](https://mlsanity.com/paper/2002.04783/) (2020)
- [Stochastic Wasserstein Barycenters](https://mlsanity.com/paper/1802.05757/) (2018)
- [Wasserstein barycenters can be computed in polynomial time in fixed dimension](https://mlsanity.com/paper/2006.08012/) (2020)
- [Improved and Simplified Inapproximability for k-means](https://mlsanity.com/paper/1509.00916/) (2015)
- [Discrete Wasserstein Barycenters: Optimal Transport for Discrete Data](https://mlsanity.com/paper/1507.07218/) (2015)
- [On Coresets for Fair Clustering in Metric and Euclidean Spaces and Their Applications](https://mlsanity.com/paper/2007.10137/) (2020)
- [The Power of Uniform Sampling for Coresets](https://mlsanity.com/paper/2209.01901/) (2022)
- [Local Search Yields a PTAS for k-Means in Doubling Metrics](https://mlsanity.com/paper/1603.08976/) (2016)
- [Bayesian Learning with Wasserstein Barycenters](https://mlsanity.com/paper/1805.10833/) (2018)
- [Local search yields approximation schemes for k-means and k-median in Euclidean and minor-free metrics](https://mlsanity.com/paper/1603.09535/) (2016)
- [Faster Algorithms for the Constrained k-means Problem](https://mlsanity.com/paper/1504.02564/) (2015)
- [On the Computational Complexity of Finding a Sparse Wasserstein Barycenter](https://mlsanity.com/paper/1910.07568/) (2019)
- [A Unified Framework for Clustering Constrained Data without Locality Property](https://mlsanity.com/paper/1810.01049/) (2018)
- [Approximate Algorithms For k-Sparse Wasserstein Barycenter With Outliers](https://mlsanity.com/paper/2404.13401/) (2024)
- [New Approximation Algorithms for Fair k-median Problem](https://mlsanity.com/paper/2202.06259/) (2022)

## Built on by (most cited first, 1 of 1)

- [A Sub-4 Approximation for Fair k-Means](https://mlsanity.com/paper/2609.07974/) (2026)

## Abstract (arXiv)

The fairness of clustering algorithms has gained widespread attention across various areas, including 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 optimal locations of k centers is a quite challenging task. 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.