kmeans_two_worst_case_ratio
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