Research map / Learning theory and algorithms / Clustering

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

ICLR 2025 · Learning theory and algorithms › Clustering · approach: Fair clustering approximation · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes a Relax-and-Merge framework that relaxes the number of centers via an epsilon-approximate centroid set, solves a fair LP, then merges with vanilla k-means, yielding improved approximation for fair k-means, k-sparse Wasserstein barycenter, and strictly fair k-means.

Problem

Fair k-means clustering in Euclidean space with per-cluster group proportion bounds, its k-sparse Wasserstein barycenter special case, and strictly fair k-means, where finding center locations under fairness constraints is hard due to loss of Voronoi locality.

Approach

Shift fairness handling into the center-location stage: build an epsilon-approximate centroid set as a relaxed candidate center set, solve an LP for fair fractional assignments, move candidates to their fair cluster centroids, then run vanilla k-means on these centroids to merge down to k centers.

Key results

• Theoretical guarantee of (1+4rho+O(eps)) for fair k-means and k-sparse WB, improving to (5+O(eps)) with a PTAS for k-means, versus (2+sqrt(rho))^2 prior work.
• Strictly fair k-means without violation achieves (2+6rho) approximation, improving over prior (2+sqrt(rho))^2 bound.
• Empirically, the algorithm yields lowest (alpha,beta)-fair k-means cost compared with NIPS19 and ORL21 across datasets; sparse WB cost is 10%-30% lower than IJCAI24 in most cases.

Measured effects reported in the paper

Surprising findings

• Sampling 50% of the relaxed candidate set T increases cost by no more than about 10% in most cases, suggesting many candidate centers receive zero weight after the LP.

Limitations

• No integral solution without violation is known for the general fair k-means case (open problem stated by authors).
• Approximate centroid set size grows as eps^-d, and the theoretical construction is replaced by a heuristic (kd-tree plus sampling) in experiments.
• Dimension d is assumed constant for theoretical guarantees; the general-metric extension has weaker bounds than prior work.

Experimental setup

Datasets: Bank Adult Census creditcard Biodeg Breastcancer Moons Hypercube Cluto Complex

Benchmarks: Bank Adult Census creditcard Biodeg Breastcancer Moons Hypercube Cluto Complex

Metrics: clustering cost running time approximation ratio

Baselines: NIPS19 ORL21 IJCAI24

Builds on: k-means++ epsilon-approximate centroid set fairlet decomposition fair k-means LP rounding (NIPS19)

Closest papers by meaning

• KFC: A Scalable Approximation Algorithm for $k$−center Fair Clustering (NeurIPS 2020 · similarity 0.92)
• Better Algorithms for Individually Fair $k$-Clustering (NeurIPS 2021 · similarity 0.91)
• Individual Fairness for k-Clustering (ICML 2020 · similarity 0.90)
• Parameterized Approximation Schemes for Fair-Range Clustering (NeurIPS 2024 · similarity 0.90)
• Towards Fairer Centroids in K-means Clustering (AAAI 2024 · similarity 0.89)
• Fair Clustering via Alignment (ICML 2025 · similarity 0.89)