A Sub-4 Approximation for Fair $k$-Means
Kangke Cheng, Guanlin Mo, Shihong Song, Hu Ding
cs.CG · cs.LG
Quick verdict
Claims first sub-4 (3.8427+O(ε)) ratio for fractional fair k-means via opening-LP gap; proof chain reads sound; incremental but real over Song et al. 2025.
Summary
This theory paper improves the best known approximation guarantee for fair k-means clustering in Euclidean space, where every cluster must contain between β_i and α_i of each protected group. Building on the relax-and-merge framework of Song et al. (2025), the authors add center-opening variables to the fair assignment LP over an approximate centroid set, allowing them to invoke the integrality gap Γ ≈ 6.357 of the standard Euclidean k-means opening LP to bound the cost of merging fractional clusters down to k centers. A weighted k-means subroutine is run on the relaxation's weighted centroids and on a family of shifted input copies; a convex combination of the three resulting bounds (Lemma 11) cancels the uncontrolled displacement terms and yields 1 + (3 − 1/Γ)ρ + O(ε) for any ρ-approximate subroutine — 3.8427 + O(ε) with a PTAS, improving the previous 5 + O(ε). Appendix B sharpens this to 3.8368 + O(ε) using Γ₀ ≈ 6.129 of Grandoni et al. (2022). Solutions satisfy fairness exactly, but assignments are fractional; integral roundings keep the cost and violate fairness additively by at most 4Δ+3 (overlapping groups) or 2 (partition). The same guarantee extends to k-sparse Wasserstein barycenters. The work is purely theoretical: no implementation or experiments.
Review complete
Assessment at a glance
3
risk flags identified
● high 0
● medium 1
● low 2
5 strengths · 5 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- For any ρ-approximate weighted k-means subroutine, fractional fair k-means is solvable within 1 + (3 − 1/Γ)ρ + O(ε) of the integral fair optimum, with Γ ≈ 6.357 (Theorem 1).
- With a PTAS subroutine the ratio is 4 − 1/Γ + O(ε) ≈ 3.8427 + O(ε), improving the previous 1 + 4ρ (5 + O(ε)) of Song et al. (2025) to below 4.
- Using the refined LP-relative constant Γ₀ ≈ 6.129 of Grandoni et al. (2022), transferable to this setting (Appendix B), the ratio becomes 3.8368 + O(ε) (Corollary 17).
- The returned centers admit integral assignments with no cost increase and additive fairness violation at most 4Δ+3 (overlapping groups) or 2 (partition case, O(n³k²) time) (Corollaries 2–3).
- The same approximation guarantee extends to the k-sparse Wasserstein barycenter problem (Theorem 15), and the framework's ρ-coefficient cannot go below 8/3 within Lemma 11 (γ > 3).
Strengths
Genuine milestone with clean proof architecture
Theorem 1 improves 1+4ρ (Song et al. 2025) to 1+(3−1/Γ)ρ+O(ε); the key move (Lemma 7) shows the fair relaxation's optimal solution is feasible for the standard opening LP on auxiliary demands νp with facilities π(T), so the Ahmadian et al. (2020) gap Γ ≈ 6.357 bounds the merge cost via OPTν ≤ Γ(CT − Cν).
Inline-verifiable algebra
Lemma 11's convex combination checks out exactly: the weights θ1, θ2, θ3 sum to 1 (numerator 3γ²−γ = γ(3γ−1)), both Cν and Ce coefficients cancel at λ* = (γ+1)/(2(γ−1)), and the residual constant is (3γ−1)²/(γ(3γ−1)) = 3−1/γ, giving 3.8427 at γ = Γ = 6.357; the Cauchy–Schwarz bound |Ce| ≤ √(Cν·OPT) is used correctly.
Honest scoping throughout
Reusable technique and extension
Transparent AI-assistance disclosure
Weaknesses
Main guarantee is for fractional assignments
Incremental over Song et al. (2025)
No empirical evidence at all
Dependence on external constants with unverifiable-from-text hypotheses
Design oddity: unnecessary grid
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
The paper studies (α, β)-fair k-means (Problem 4, Bera et al. 2019): given n points in R^d with m possibly overlapping protected groups, choose at most k continuous centers and an assignment such that every cluster's fraction of group i lies in [βᵢ, αᵢ], minimizing squared-distance cost. The headline claim (Theorem 1) is a randomized polynomial-time algorithm returning a *fractional* assignment with cost at most (1 + (3 − 1/Γ)ρ + O(ε))·OPT, where ρ is the guarantee of any weighted k-means subroutine and Γ ≈ 6.357 is the integrality gap of the Euclidean k-means opening LP (Ahmadian et al. 2020). With a PTAS subroutine this reads 3.8427 + O(ε) — the first ratio below 4 — improving the 1 + 4ρ (i.e., 5 + O(ε)) of Song et al. (2025). Table 1 situates this among prior ratios (Bera et al. 9; Schmidt et al. 6.5, two groups only; Böhm et al. 9 under strictly fair integral solutions; Yang–Ding 9 for k-sparse barycenters). Appendix B replaces Γ with Γ₀ ≈ 6.129 from Grandoni et al. (2022), giving 3.8368 + O(ε) (Corollary 17). Two cost-nonincreasing roundings (Corollaries 2–3) produce integral assignments with additive fairness violation at most 4Δ+3 (overlapping groups, Δ = max groups per point) or 2 (partition, min-cost circulation, O(n³k²)). Theorem 15 transfers the same ratio to k-sparse Wasserstein barycenters. Claim discipline is good: the fractional/integral split is stated up front, and the conclusion concedes the technique cannot push the ρ-coefficient below 8/3 since Lemma 11 requires γ > 3.
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 5 strengths & 5 weaknesses, analyzed in detail
- 3 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What approximation ratio does this paper achieve for fair k-means?
It guarantees cost at most 1 + (3 − 1/Γ)ρ + O(ε) times the optimum, where Γ ≈ 6.357 is the known integrality gap of the Euclidean k-means opening LP and ρ is the guarantee of the weighted k-means subroutine used. With a PTAS subroutine this is 3.8427 + O(ε) — the first ratio below 4, down from the previous 5 + O(ε); using a refined constant Γ₀ ≈ 6.129 (Grandoni et al. 2022) it becomes 3.8368 + O(ε).
Are the clustering assignments integral?
No. The main theorem returns a fractional assignment that satisfies the fairness constraints exactly but may split a point across several clusters. Two roundings convert it to an integral assignment without increasing cost, at the price of an additive fairness violation of at most 4Δ+3 when protected groups overlap (Δ = maximum number of groups per point) or at most 2 when they form a partition.
Does the result also apply to Wasserstein barycenters?
Yes. Reading each input distribution as a protected group of weighted atoms turns any transport plan into an exactly fair assignment, so the same 1 + (3 − 1/Γ)ρ + O(ε) guarantee transfers to the k-sparse Wasserstein barycenter problem (Theorem 15).
Is there code or an experimental evaluation available?
No. The paper is purely theoretical: it presents algorithms, proofs, and running-time bounds, but no implementation, datasets, or experiments, and no code artifact is mentioned.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- The closed-form expression for Γ₀ in Appendix B renders nested radicals as garbled text in PDF extraction ('p3' fragments); the numeric value 6.129023734395501 is legible, so all ratio computations use the number.
- Table 1 in the extraction is visually interleaved; its ratio entries (9, 6.5, 9, 9, 5, 3.8427, 3.8368) and setting labels were reconstructed and cross-checked against the surrounding prose and the references.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.