AFTD Auto-Formalizing Theoretical Domains

kmeans_two_competitive_ratios

def

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 }
See it in the graphDiscuss this resultChallenge it