Lune

ICLR2025Top-tier venue

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

Shihong Song, Guanlin Mo, Hu Ding

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.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Finding Wasserstein Ball Center: Efficient Algorithm and The Applications in Fairness cites Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast Algorithm
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers1

  1. Finding Wasserstein Ball Center: Efficient Algorithm and The Applications in FairnessYuntao Wang, Yuxuan Li, Qingyuan Yang, Hu DingICML 2025

Builds on3

  1. Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast AlgorithmTianyi Lin, Nhat Ho, Xi Chen, Marco Cuturi et al.NeurIPS 2020 · 60 citations
  2. The Power of Uniform Sampling for CoresetsVladimir Braverman, Vincent Cohen-Addad, Shaofeng H.-C. Jiang, Robert Krauthgamer et al.FOCS 2022 · 20 citations
  3. Approximating Fair Clustering with Cascaded Norm ObjectivesEden Chlamtác, Yury Makarychev, Ali VakilianSODA 2022 · 15 citations

Related papers

  1. KFC: A Scalable Approximation Algorithm for kk-center Fair ClusteringElfarouk Harb, Ho Shan LamNeurIPS 2020 · 28 citations
  2. Approximate Group Fairness for ClusteringBo Li, Lijun Li, Ankang Sun, Chenhao Wang et al.ICML 2021 · 28 citations
  3. Fair Clustering via AlignmentKunwoong Kim, Jihu Lee, Sangchul Park, Yongdai KimICML 2025
  4. Fast and Accurate Fair k-Center Clustering in Doubling MetricsMatteo Ceccarello, Andrea Pietracaprina, Geppino PucciWWW 2024 · 10 citations
  5. Approximation Algorithms for Fair Range ClusteringSèdjro Salomon Hotegni, Sepideh Mahabadi, Ali VakilianICML 2023 · 25 citations
Dusk over the sea between two cliffs drawn in fine vertical lines