PaperlayerView exact revision on arXiv

Source-linked AI summary

A Sub-4 Approximation for Fair $k$-Means

Kangke Cheng, Guanlin Mo, Shihong Song, Hu Ding

arXiv:2609.07974v1cs.CGcs.LG

TL;DR

Fair k-means must balance protected-group representation, which disrupts nearest-center assignments and complicates center selection. This paper combines an LP relaxation with candidate-center constructions, obtaining a below-4 approximation with a PTAS and extending its guarantees to k-sparse Wasserstein barycenters.

  • Problem

    Fairness constraints can require assigning points to non-nearest centers, so selecting at most k centers while meeting group bounds makes fair k-means harder than unconstrained clustering.

    Source: §1.1 · p. 2, §1.2 · p. 2

  • Method

    The algorithm uses a fair center-opening relaxation and weighted k-means on cluster-derived and shifted instances to construct candidate centers, then combines their cost bounds.

    Source: §1.2 · p. 3, §4.5 · p. 18

  • Results

    3.8368 + O(ϵ) with a PTAS and the refined LP-relative bound; the fractional solution satisfies fairness exactly, and rounding can preserve cost with bounded additive violation.

    Source: §1.2 · pp. 3–4

  • Takeaways & Limitations

    The guarantees also transfer to k-sparse Wasserstein barycenters by interpreting transport plans as fair assignments of weighted atoms.

    Source: §6 · p. 26

    The merge analysis applies for γ > 3; within that range its ratio stays above 1 + 8/3ρ, so smaller ratios require a different merge-step treatment.

    Source: §6 · p. 26

Abstract

from arXiv · show

Fairness in clustering has attracted sustained research interest, motivated by the need to ensure equitable representation of protected groups in machine learning applications. We study fair $k$-means clustering in Euclidean space, where the proportion of each protected group in every cluster must lie within specified lower and upper bounds. These constraints make it challenging to determine both cluster centers and point assignments. We propose an approximation algorithm that combines a linear programming relaxation with geometric transformations of the input to construct candidate center sets. Given a $\rho$-approximate algorithm for weighted $k$-means and any $\epsilon>0$, our algorithm returns a fractional solution whose cost is at most $1+(3-1/\Gamma)\rho+O(\epsilon)$ times the optimal integral fair cost, where $\Gamma\approx6.357$ is an upper bound on the integrality gap of the standard Euclidean $k$-means LP. With a PTAS as the subroutine, the approximation ratio becomes $3.8427+O(\epsilon)$, improving the previous factor of $5+O(\epsilon)$ to below $4$. The solution satisfies all fairness constraints exactly and can be rounded to an integral assignment with a bounded additive violation of fairness and no increase in cost. The same approximation guarantee extends to the $k$-sparse Wasserstein barycenter problem.

1 Introduction

Fairness constraints disrupt nearest-center assignments, making it harder to determine where centers can lie. The paper combines a fair center-opening relaxation with candidate-center constructions to improve fair k-means guarantees and extend them to k-sparse Wasserstein barycenters.

1.1 Background and Motivation

  • Fairness breaks the link between centers and Voronoi clusters, so a solution may assign points to non-nearest centers and makes optimal center locations harder to characterize.An approximate centroid set supplies representatives close to the centroid of every possible subset of input points.Source: §1.1 · p. 2

1.2 Overview and Main Result

  • The algorithm combines a fair center-opening relaxation, whose induced auxiliary k-means instance permits use of the Euclidean LP gap, with weighted centroids and shifted input instances as candidate centers.Candidate sets from different regimes yield bounds that are combined to control the merge cost.Source: §1.2 · pp. 2–3
  • Both roundings keep centers fixed and never raise cost; the cited guarantees report additive violation at most 4∆+3 and at most 2, while each rounding costs one unit of violation.Source: §1.2 · p. 4
  • 3.8368 + O(ϵ) with a PTAS, using Γ0 ≈ 6.129, improves the previous 5 + O(ϵ) ratio to below 4.The general guarantee has coefficient 3 −1/Γ ≈ 2.843 on ρ; Grandoni et al. (2022) provide the refined LP-relative bound.Source: §1.2 · p. 4
  • The guarantees extend to k-sparse Wasserstein barycenters by treating input distributions as protected groups of weighted atoms and using indexed atom copies to cover induced weighted centroids.A fixed-support transport LP converts the returned support into a barycenter.Source: §1.1 · p. 2, §1.2 · p. 5

1.3 Related Work

  • Prior fair-clustering work includes algorithms, coresets, and alternative fairness notions; Song et al. (2025) give a 1+4ρ+O(ϵ) ratio for continuous Euclidean fair k-means.The standard center-opening LP’s Euclidean integrality gap is at most Γ ≈ 6.357; Grandoni et al. (2022) sharpen the LP-relative guarantee to Γ0 ≈ 6.129 under a restricted facility domain.Source: §1.3 · p. 5

2 Preliminaries

The preliminaries define fair k-means assignments and costs, then introduce centroid approximations and the center-opening LP used in the analysis.

2 Preliminaries

  • An assignment sends each point’s unit mass across centers; it is integral when entries are 0 or 1, and fractional otherwise.Without fairness constraints, minimum cost assigns every point to its nearest center.Source: §2 · p. 6
  • Fair k-means seeks at most k centers and an assignment minimizing cost while meeting each protected group’s per-cluster bounds.The setup assumes an exactly fair integral solution exists; groups may overlap, with Δ denoting the largest number containing one point.Source: §2 · pp. 6–7
  • The centroid identity quantifies the cost of moving a weighted set’s centroid, while an approximate centroid set covers centroids of every nonempty subset.The coverage applies to clusters a fair solution could form, not only to Voronoi cells.Source: §2 · p. 7
  • The center-opening LP assigns demands to facilities and fractionally opens facilities under a budget of k; its integrality gap also bounds the continuous-center optimum.A weighted k-means subroutine instead returns at most k centers with cost at most ρ times the best such center set’s cost.Source: §2 · p. 8

3 The Algorithm

The algorithm relaxes fair center selection over an approximate centroid set, then uses weighted k-means on centroids and shifted inputs to produce center candidates. It solves a fair assignment LP for each candidate set and returns the cheapest solution.

3 The Algorithm

  • The algorithm first solves a fair center-opening LP over an approximate centroid set, then forms weighted centroids and shifted copies of the input.It runs weighted k-means on the centroids and each shifted copy, then returns the cheapest fair assignment over the resulting center sets.Source: §3 · p. 8
  • The LP treats each approximate-centroid candidate as a facility, imposing fairness constraints and a fractional opening budget of k.Its assignment may involve more than k candidates; the opening variables support the later analysis of merging to at most k centers.Source: §3 · pp. 8–9
  • For each positively weighted candidate, the algorithm forms the weighted centroid of its assigned points while retaining its weight and index.It also defines each point’s weighted mean of the centroids serving it, then shifts the point away from that mean by a fraction of the displacement.Source: §3 · p. 9
  • A grid in [1/2, 1] supplies shifted instances; weighted k-means returns at most k centers for each instance and for the weighted centroids.The algorithm solves the fair assignment LP on each resulting center set and keeps the least-cost solution.Source: §3 · pp. 9–10

10 end

The section closes with the algorithm’s returned pair and a brief complexity and approximation-error summary.

10 end

  • The algorithm returns a center set and its fractional assignment, choosing the pair with minimum assignment cost among its candidates.Source: §10 · p. 10
  • For fixed δ, the algorithm uses polynomially many LP solves and weighted k-means calls; the chosen δ yields O(ϵ) total error.In fixed dimension, the candidate set is polynomial in size and a subroutine with ρ = 1 + O(ϵ) is available.Source: §10 · p. 10

4 Approximation Analysis

The analysis combines bounds on the relaxation and candidate center sets to obtain an approximation guarantee in terms of OPT. It establishes a 1+(3−1/Γ)ρ+O(ε) bound with exact fairness and at most k centers, and polynomial running time for fixed ε and ρ when the weighted k-means subroutine is polynomial-time.

4.1 Candidate-Set Cost and Fair Routing

  • For every nonempty center set S, routing each candidate to its nearest center yields a feasible fair assignment whose cost separates into an S-independent term and the cost of covering weighted centroids.Fairness is preserved by summing each candidate’s group bounds over the candidates routed to a center, including when groups overlap.Source: §4.1 · p. 12

4.2 The Auxiliary Instance of Weighted Means

  • The weighted-mean identity gives 0 ≤ Cν ≤ CT and OPTν ≤ Γ(CT − Cν), also for rationally weighted input.The identity equates the weighted squared displacement between π(t) and νp with CT − Cν.Source: §4.2 · pp. 13–14

4.3 Two Bounds for Sπ

  • The fair assignment on Sπ satisfies two bounds: one follows from the weighted k-means approximation, while the other compares π(T) with the optimal fair centers and retains the cross term Ce.The analysis keeps Ce explicit for elimination in the convex combination.Source: §4.3 · pp. 15–17

4.4 A Bound for Sλ

  • For each shifted instance Pλ, the k-means call produces Sλ with a bound on fair-assignment cost, using a fair assignment formed by routing whole optimal clusters.The shifted points are pλ, and the resulting integral assignment is fair because it unions exactly fair optimal clusters.Source: §4.4 · p. 17

4.5 Convex Combination

  • A convex combination of the candidate-set bounds cancels Cν and Ce, leaving a bound in OPT alone; the algorithm’s cheapest candidate is no worse than that combination.The combination uses a generic γ > 3, with the opening-LP gap entering through the factor γ + 1.Source: §4.5 · p. 18
  • Choosing weights to cancel the cost terms and replacing the ideal shift with a nearby grid value keeps the bound's error O(ε).The selected weights sum to one, and the grid replacement changes the bound by O(ρδ), with δ=ε/(ρΓ).Source: §4.5 · pp. 19–21
  • The convex-combination analysis yields an approximation factor of 1+(3-1/Γ)ρ+O(ε).The theorem follows by applying the convex-combination bound with γ=Γ and δ=ε/(ρΓ).Source: §4.5 · pp. 20–21
  • The returned center set has at most k centers, and its assignment satisfies the fairness constraints exactly.The weighted k-means calls return at most k centers, and the fair assignment LP is solved exactly for each candidate.Source: §4.5 · p. 21

4.6 Running Time

  • For fixed ε and ρ, the algorithm runs in polynomial time under a polynomial-time weighted k-means subroutine.The running-time analysis covers the unrestricted-dimension setting as well as the direct analysis in input dimension.Source: §4.6 · pp. 22–23

5 k-Sparse Wasserstein Barycenters

The section converts the k-sparse Wasserstein barycenter problem into weighted fair clustering, then uses candidate centers to construct a feasible solution and recover a barycenter on a bounded support.

5 k-Sparse Wasserstein Barycenters

  • Equal group bounds require each distribution to contribute equal transported mass at every center, linking fair assignments to barycenter transports.On a fixed center set, the minimum barycenter cost is 1/m of the minimum exactly fair fractional assignment cost.Source: §5 · p. 23
  • The candidate set approximates fractional-weight centroids by sampled means, with duplicated atoms allowing samples to be handled as subsets.Lemma 13 supplies the weighted-centroid approximation used to cover centers induced by optimal transports.Source: §5 · p. 24
  • (1 + δ)mOPTWB bounds the cost of a feasible solution to LP (11) on the weighted instance.The instance uses α_i = β_i = 1/m.Source: §5 · p. 24
  • The algorithm runs on the weighted atoms and candidate set, then solves a fixed-support transport LP to obtain a barycenter.Theorem 15 states a randomized polynomial-time algorithm that returns a distribution supported on at most k points with high probability.Source: §5 · p. 25

6 Conclusion

The paper gives a sub-4 approximation for fair k-means with fractional assignments. Its analysis ties the merge cost to the center-opening LP gap, while cost-nonincreasing rounding yields integral assignments with bounded additive fairness violation.

6 Conclusion

  • The guarantee is 1 + (3 - 1/Γ)ρ + O(ϵ), or 4 - 1/Γ + O(ϵ) with a PTAS subroutine.The center-opening LP gap bounds the cost of merging the relaxation’s clusters.Source: §6 · p. 26
  • Cost-nonincreasing roundings produce integral assignments with bounded additive fairness violation.The multiset candidate set also transfers the guarantees to k-sparse Wasserstein barycenters.Source: §6 · p. 26
  • The merge analysis requires γ > 3, and its bound remains above 1 + 8/3ρ throughout that range.Consequently, reaching smaller ratios requires a different treatment of the merge step, not merely a better LP gap.Source: §6 · p. 26

Appendix A. Dimension Reduction and Running Time

The appendix uses a Johnson–Lindenstrauss projection to make the candidate-center construction practical in high dimensions, then lifts the solution while controlling cost distortion and preserving fairness.

Appendix A. Dimension Reduction and Running Time

  • A random projection to dimension O(δ^-2 log n) preserves pairwise squared distances within 1 ± η with high probability.The resulting candidate-set construction and the stated LP and weighted k-means calls have polynomial size and running time.Source: Appendix A · pp. 26–27
  • The projection and lifting multiply the cost bound by at most 1 + 4δ.The distortion parameter is set to η = δ.Source: Appendix A · p. 27
  • Lifting preserves exact fairness because it leaves the assignment matrix unchanged.If the original dimension is already below the target dimension, the identity map incurs no distortion.Source: Appendix A · p. 27

Appendix B. Strengthening via the LP-Relative Bound of Grandoni et al.

The appendix applies a refined LP-relative rounding bound to strengthen the approximation guarantees. It adapts the bound to the proof’s facility domain and carries the improved result to integral assignments and Wasserstein barycenters.

Appendix B. Strengthening via the LP-Relative Bound of Grandoni et al.

  • The refined constant replaces Γ in the merge analysis, while the algorithm and the rest of the analysis remain unchanged.The constant enters the analysis through the opening-LP bound.Source: Appendix B · pp. 27–29
  • The refined LP-relative result restricts facilities to means of bounded-size samples from the demand multiset, so the proof adds its candidate locations as demands.Replicating the original demands makes the added candidates’ service cost negligible in the limit.Source: Appendix B · pp. 28–29
  • The added demands are assigned using proportions from the relaxation, yielding the refined opening-LP bound after replication grows without bound.For fixed τ, the auxiliary service cost is independent of the replication count; taking the count to infinity and then τ to zero gives OPTν ≤ Γ0(CT − Cν).Source: Appendix B · pp. 28–29
  • With ρ = 1 + O(ϵ), the strengthened factor is 4 - 1/Γ0 + O(ϵ), and the same bound applies to integral assignments and barycenters.For barycenters, the weighted assignment bound transfers through the transport–assignment correspondence.Source: Appendix B · pp. 29–30

Appendix C. Proof of Lemma 13

The proof normalizes the weights and uses independent sampling to find a candidate close to the weighted centroid. It then applies the centroid identity and rescales to recover Equation (39).

Appendix C. Proof of Lemma 13

  • When σ2 = 0, every positive-weight atom equals c, and Definition (8) for a singleton gives c ∈ T.The proof otherwise assumes σ2 > 0.Source: Appendix C · p. 30
  • Independent draws from the normalized weights form a unit-weight indexed sample, with repeats represented by distinct indexed copies.The sample mean is the weighted centroid because each draw has expectation c.Source: Appendix C · p. 30
  • For r ≥ 4/δ, some realization yields a candidate t with ∥t − c∥2 < δσ2, after which the centroid identity is applied.The proof first chooses a candidate satisfying Equation (45) for each realization and uses the squared triangle inequality.Source: Appendix C · pp. 30–31
  • Rescaling the weights returns the normalized argument to Equation (39) in its original form.Both sides scale linearly with the weights, allowing normalization before the proof.Source: Appendix C · pp. 30–31

Appendix D. Fixed-Support Wasserstein Barycenter

For a fixed support set, a linear program chooses a shared barycenter mass vector and transports from each input atom. Its solution defines a barycenter supported on at most k points.

Appendix D. Fixed-Support Wasserstein Barycenter

  • The fixed-support linear program finds barycenter masses and transports from every input atom to each support point.The support set S has size at most k.Source: Appendix D · p. 31
  • A single mass vector shared across all input distributions makes the solution one common barycenter, with optimal value equal to the minimum fixed-support barycenter cost.The transports satisfy constraints (33).Source: Appendix D · p. 31
  • The linear program has O(|S| |P|) variables and is solvable in polynomial time; removing zero-mass support points leaves at most k points.The resulting barycenter has support size at most |S| ≤ k.Source: Appendix D · p. 31
Loading 2609.07974v1…