kmeans_two_competitive_ratios
The 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 Euclidean space R^d with OPT₂(X) > 0 such that r = E[Phi₂]/OPT₂(X).
Statement
def kmeans_two_competitive_ratios : Set ℝ- Defined in
- arXiv:2611.14573 Section 1.1
- Verified
- 13 Nov 2026
- Axioms
- none listed
- Built on 2
- kmeans_opt_twoThe optimal 2-means cost OPT₂(X) of a finite set of points X is the infimum over all pairs of centers c₁, c₂ of the 2-means cost of X with…
- kmeans_plus_plus_two_expected_costThe expected cost E[Phi₂] of two centers chosen by k-means++ on a finite set X is the average over uniformly chosen first center c₁ in X…
- Used by 1
- kmeans_two_worst_case_ratioThe 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…
Read back from the Lean
kmeans_two_competitive_ratios is defined as the set of all real numbers $r$ such that there exists a dimension $d \in \mathbb{N}$ and a finite subset $X \subseteq \text{EuclideanSpace } \mathbb{R} (\text{Fin } d)$ satisfying:
1. The optimal 2-means cost of $X$ (kmeans_opt_two X) is strictly positive; and
2. $r$ equals the ratio of the expected 2-means cost of $X$ under 2-means++ seeding (kmeans_plus_plus_two_expected_cost X) to the optimal 2-means cost of $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 set of competitive ratios E[Phi₂] / OPT₂(X) achieved by k-means++ on finite sets X in Euclidean spaces with OPT₂(X) > 0. -/ def kmeans_two_competitive_ratios : Set ℝ := { r : ℝ | ∃ (d : ℕ) (X : Finset (EuclideanSpace ℝ (Fin d))), 0 < kmeans_opt_two X ∧ r = kmeans_plus_plus_two_expected_cost X / kmeans_opt_two X }