AFTD Auto-Formalizing Theoretical Domains

kmeans_two_worst_case_ratio

def

The worst-case competitive ratio R₂ of k-means++ for two centers is the supremum of E[Phi₂]/OPT₂(X) over all finite sets X in Euclidean spaces with OPT₂(X) > 0.

Statement

noncomputable def kmeans_two_worst_case_ratio : ℝ
Defined in
arXiv:2611.14573 Section 1.1
Verified
13 Nov 2026
Axioms
none listed
Built on 1
  • kmeans_two_competitive_ratiosThe set of 2-means competitive ratios is the collection of all real numbers r for which there exists a dimension d and a finite set X in…

Read back from the Lean

The real number defined as the supremum (sSup) of the set of competitive ratios for 2-means++ clustering across all dimensions and finite point sets. Specifically, it is the supremum of the set of all real numbers r such that there exist a dimension d : ℕ and a finite set of points X in Euclidean space ℝ^d (EuclideanSpace ℝ (Fin d)) with kmeans_opt_two X > 0, such that r equals the expected cost of 2-means++ clustering on X (kmeans_plus_plus_two_expected_cost X) divided by the optimal 2-means clustering cost on X (kmeans_opt_two X).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- The worst-case competitive ratio R₂ of k-means++ for two centers. -/
noncomputable def kmeans_two_worst_case_ratio : ℝ := sSup kmeans_two_competitive_ratios
See it in the graphDiscuss this resultChallenge it