Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Selecting feasible rational clustering candidates and enumerating two-edge threshold labels

Definition
StableMSR_Recovery_Supplement_CandidateSelection

by lreyzin · Nov 19, 2026 · Mathlib 0df444a (Lean v4.33.1)

algorithmsclusteringcomputational-complexity

A generic minimum-cost selection over a polynomial candidate list, and a concrete candidate list obtained by enumerating the rational input distances and grouping by two-edge threshold reachability. All loops are bounded by parsed input or lists.

Definition code
import Definitions.Def_StableMSR_Recovery_Supplement_BinaryRecovery
set_option autoImplicit false
namespace StableMSR.Recovery.Supplement.BinaryRecovery
open BinaryVerifier

/-- The search list needs to contain a labeling of each stable solution. -/
def ContainsStable (F : Input → List (List ℕ)) (γ : ℚ) : Prop :=
  ∀ I : RationalInput, I.Valid → ∀ O : Partition I.n, Stable I.dist I.k γ O →
    ∃ l ∈ F (fieldsOf I), l.length = I.n ∧ labelsPartition I.n I.k l = O

def eligible (a : Input) (l : List ℕ) : Bool :=
  decide (l.length=a.1) && labelsOK a.2.1 l

/-- Compute a feasible minimum among the listed labelings, using exact rational costs. -/
def select (a : Input) (ls : List (List ℕ)) : List ℕ :=
  let good := ls.filter (eligible a)
  let val := total a.1 a.2.1 a.2.2
  (good.filter (fun x => good.all (fun y => decide (val x ≤ val y)))).head?.getD []

/-- The enumeration length is bounded by the actual table length even on malformed data. -/
def points (a : Input) : List ℕ := (List.range a.2.2.length).take a.1

def twoHop (a : Input) (t : ℚ) (i j : ℕ) : Bool :=
  (points a).any fun z => decide (distAt a.1 a.2.2 i z ≤ t) && decide (distAt a.1 a.2.2 z j ≤ t)

def keys (a : Input) (t : ℚ) : List ℕ :=
  (points a).map fun i => ((points a).filter (twoHop a t i)).head?.getD 0

def compact (ps ks : List ℕ) : List ℕ :=
  let palette := ps.filter (fun j => ks.contains j)
  ks.map (fun i => palette.idxOf i)

def thresholdCandidates (a : Input) : List (List ℕ) := a.2.2.map fun t => compact (points a) (keys a t)
end StableMSR.Recovery.Supplement.BinaryRecovery
Source
S. Ravichandran and L. Reyzin, Exact Sum-of-Radii Clustering under Any Constant Stability, Section 3 and Appendix C.4. https://arxiv.org/abs/2611.03547 . The common-radius two-edge criterion is deduced from the published center and intercluster separation statements.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me