The -means problem asks for at most centers in minimizing the sum of squared distances from input points to their nearest centers. When the points are people, the composition of a cluster can matter as much as its cost: a clustering used for loan approval or school assignment may concentrate a protected group in one cluster. The group-balance model of Chierichetti, Kumar, Lattanzi and Vassilvitskii (CKLV17), generalized by Bera, Chakrabarty, Flores and Negahbani (BCFN19) to overlapping groups with lower and upper bounds, requires every cluster to contain each group in a prescribed proportion. The same model contains the -sparse Wasserstein barycenter problem, a compact summary of several probability distributions supported on points.
Fairness constraints break the locality on which most -means algorithms rely: points need not go to their nearest center, so it is unclear where an optimal solution places its centers.
Timeline of approximation ratios for fair -means, where is the ratio of a weighted -means subroutine:
An instance consists of points in , groups that may overlap, an integer , and bounds . A solution is a family of at most centers with an assignment matrix : nonnegative entries , every row summing to one. It is integral if every entry is or and fractional otherwise. The cluster of has weight , of which group contributes ; the assignment is -fair if for every and . Its cost is
and are the infima of the cost over fair integral and fair fractional solutions; . For a fixed center family, the minimum-cost fair fractional assignment is a linear program, the fair assignment LP.
Algorithm 1 takes a -approximate weighted -means algorithm and . It sets and , solves the fair assignment LP on a large candidate set, and then improves a fair fractional clustering with many small fragment clusters by a Frank–Wolfe-type loop of linear programs (LP (29)) that lowers the drift-regularized cost . Finally it runs the -means algorithm once on the weighted centroids of the fragment clusters and re-solves the fair assignment LP on the returned centers.
The paper presents four main results: refTheorem 3 gives the fair -means approximation, refTheorem 4 the -sparse Wasserstein barycenter approximation, refTheorem 7 the matching hardness threshold, and refTheorem 32 the extension to homogeneous cluster constraints. The platform allows one goal, so Theorem 3 is the goal and the other three are milestones of equal standing.
For every and there is such that for every dimension, every instance with a fair solution, all exact LP oracles and every -approximate weighted -means oracle, Algorithm 1 stops by its own test and returns at most centers with an exactly fair fractional assignment satisfying
with one -means call, at most linear programs, and every LP, the -means input and the arithmetic count bounded by .
The first fifteen milestones follow the proof (Figure 5 of the paper). First, the candidate sets of Lemma 15, part 2. Then the identities of Section 5: Lemma 17 (mixing) and Lemma 18 (column). Next, the analysis of a -stationary relaxed solution: Lemma 19 (routing), Lemma 20 (weighted means), the comparison reduction of Section 6.2, Lemma 21 (comparison bound), Lemma 22 (stationarity bound) and Lemma 23 (final cost). Then the loop: Lemmas 24–28 (initial pair, bounded iterates, one LP, descent, termination). Last, Proposition 29 (running time).
These three milestones were added on 2026-11-16 so that the mission covers every theorem of the paper.
Theorem 3 lowers the coefficient of in the best known ratio for fair -means from to . In fixed dimension a PTAS for weighted -means gives ratio , and Theorem 7 of the same paper shows that cannot be beaten in polynomial time unless P = NP. The guarantee is against , satisfies the fairness constraints exactly, and carries over to -sparse Wasserstein barycenters and to every family of homogeneous linear cluster constraints.
The result is proved in the paper. It has not been formalized. The mission produces machine-checked proofs of every theorem of the paper: the full fair -means guarantee with the drift-regularized relaxation and its Frank–Wolfe analysis, the multiset-means candidate sets, and the explicit iteration, LP-size and operation bounds; the barycenter approximation; the hardness threshold; and the extension to homogeneous linear cluster constraints.
The natural approach solves an LP on a large candidate set, clusters the centroids of the fragment clusters, and bounds the rerouting cost with the Cauchy–Schwarz inequality. That bound is tight for the argument and gives only . The loss sits in a cross term, the alignment , which depends on the unknown optimal centers. The relaxation never computes ; near-stationarity of the drift-regularized objective bounds it. Turning that into a terminating algorithm needs candidate sets accurate for every weighting at once, a potential argument with explicit constants (88, 4, 72, 288, 576), and an LP that approximates a non-linear subproblem. Each of these steps uses the centroid identity of squared Euclidean distances several times.
For Theorem 3, points live in EuclideanSpace ℝ (Fin d) and are an indexed family Fin n → E d; groups are Fin m → Finset (Fin n). Center and candidate sets are indexed families Fin s → E d, and disjoint unions are Fin.append. All points have unit weight; the -means oracle receives the centroids with weights . The centroid of a zero column is Lean's value and always carries weight . The optima are real infima, nonempty under the paper's standing assumption that the instance has a fair solution (a hypothesis of the goal).
The cost model is the paper's footnote 1. Algorithm 1 is a Lean function of a fair-LP oracle, an LP (29) oracle and a -means oracle. The LP oracles return an optimal solution whenever one exists; the -means oracle returns between and centers of cost at most times the optimum. Real-RAM operations outside the oracles are counted by explicit charges. The candidate sets are those of Lemma 15, part 2 (means of all -multisets) in every dimension. The loop runs on a budget of iterations and records whether its own stopping test ended it, and the goal asserts that it did. A cut-off loop therefore cannot satisfy the goal.
Proposition 29 is stated in a corrected form: as printed, its LP-size bounds fail when , so replaces . Lemma 15, part 2 adds .
A complete development needs the centroid identity for weighted sums in Euclidean space, the attainment of minima of weighted squared-distance sums, the existence of optimal solutions of bounded feasible linear programs (for the oracle specifications to apply), and the averaging argument of Inaba, Katoh and Imai. These are reusable beyond the mission, and contributions of them as separate lemmas are welcome.
namespace FairKMeans
/-- **Theorem 3 (Fractional fair k-means)**, p.3 (PDF 5). Cheng–Mo–Song–Ding,
arXiv:2609.07974 (held version, sha256 73e9312c…).
Let `ρ ≥ 1` and `ε ∈ (0,1]`, and `η = min{1/10, ε/(3ρ)}`. There is `c` (depending only on `ρ`
and `ε`) such that for every dimension `d`, every instance with a fair solution (p.19), every
exact fair-LP oracle, every exact LP (29) oracle and every ρ-approximate weighted k-means oracle,
Algorithm 1 (p.25) stops by its own test, returns at most `k` centers `S` and an exactly
`(α, β)`-fair fractional assignment `φ_S` with
`Cost(P, S, φ_S) ≤ (2ρ+1+ε) OPT_frac ≤ (2ρ+1+ε) OPT` (1), calls the k-means oracle exactly once,
solves at most `⌈576/η²⌉ + 3 ≤ 57604 (ρ/ε)²` linear programs, and every LP (variables plus
constraints), the k-means input and the number of real-RAM operations outside the oracles are at
most `c (n+d+m+k+2)^c`.
**Formalization Note.** "A deterministic polynomial-time algorithm … with access to a
ρ-approximation algorithm" is Algorithm 1 as a function of its oracles, in the cost model of
footnote 1 (real-RAM arithmetic counted, LP and k-means time separate). -/
theorem theorem_3 (ρ ε : ℝ) (hρ : 1 ≤ ρ) (hε : ε ∈ Set.Ioc (0 : ℝ) 1) :
∃ c : ℕ, ∀ (d n m : ℕ) (I : Instance d n m), HasFairSolution I →
∀ (fairLP : FairLPOracle d n) (lp29 : LP29Oracle d n) (KM : KMOracle d),
IsFairLPOracle I fairLP → IsLP29Oracle I lp29 → IsRhoApprox ρ I.k KM →
(alg1 ρ ε I fairLP lp29 KM).stopped ∧
(alg1 ρ ε I fairLP lp29 KM).s ≤ I.k ∧
IsAssignment (alg1 ρ ε I fairLP lp29 KM).assign ∧
IsFair I (alg1 ρ ε I fairLP lp29 KM).assign ∧
cost I (alg1 ρ ε I fairLP lp29 KM).centers (alg1 ρ ε I fairLP lp29 KM).assign ≤
(2 * ρ + 1 + ε) * OPTfrac I ∧
(2 * ρ + 1 + ε) * OPTfrac I ≤ (2 * ρ + 1 + ε) * OPT I ∧
(alg1 ρ ε I fairLP lp29 KM).kmCalls = 1 ∧
(alg1 ρ ε I fairLP lp29 KM).lpCalls ≤ ⌈576 / eta ρ ε ^ 2⌉₊ + 3 ∧
((alg1 ρ ε I fairLP lp29 KM).lpCalls : ℝ) ≤ 57604 * (ρ / ε) ^ 2 ∧
(∀ L ∈ (alg1 ρ ε I fairLP lp29 KM).lpSizes, L.1 + L.2 ≤ c * (n + d + m + I.k + 2) ^ c) ∧
(alg1 ρ ε I fairLP lp29 KM).kmInputSize ≤ c * (n + d + m + I.k + 2) ^ c ∧
(alg1 ρ ε I fairLP lp29 KM).arithOps ≤ c * (n + d + m + I.k + 2) ^ c := by sorry
end FairKMeans
Let , and . There is a constant , depending only on and , such that the following holds for every dimension , every instance with a fair solution, every exact fair-LP oracle, every exact LP (29) oracle and every -approximate weighted -means oracle. Algorithm 1, run with these,
This improves the ratio of Song, Mo and Ding; in fixed dimension, with a PTAS for weighted -means, the ratio is .
Differences from the source:
No submissions yet on this mission's goal. Log in and be the first to prove it.