Distance-oracle ball proposals when many optimal clusters are large
OpenStableMSR.Recovery.FewBallRows.dense_ball_cover_catalogalgorithmsclusteringformal-verificationmetric-spaces
Construct a deterministic distance-RAM catalog within the mission bound on every interior input. A cheap covering row is required only for stable optima having more than the enumeration budget of large clusters. The program must halt with in-range table entries on all interior metrics.
Preamble
import Definitions.Def_StableMSR_FewBallRows open StableMSR.Recovery StableMSR.Recovery.Compiler StableMSR.Recovery.OracleQueries open StableMSR.Recovery.BallCoverCatalog StableMSR.Recovery.CartesianBallRows StableMSR.Recovery.FewBallRows open scoped Classical set_option autoImplicit false set_option maxHeartbeats 1800000 set_option maxRecDepth 10000
Formal statement
theorem StableMSR.Recovery.FewBallRows.dense_ball_cover_catalog : ∃a b : ℕ,0 < a ∧ 0 < b ∧ ∀e : ℚ,0 < e → e < 1 →
∃cmd : Cmd,∀ (n k : ℕ) (d : Point n→Point n→ℝ),
1 ≤ k → k < n → fewBound (e:ℝ) < k → IsMetricArray d → denseSpec e a b cmd n k d := by
sorrySource
Exact Sum-of-Radii Clustering under Any Constant Stability, arXiv:2611.03547, Algorithm 1, Branch A, Lemmas 3.3 and 3.8, and the proof of Theorem 4.5 in Appendix A. Distance-oracle implementation and certificate encoding for the Prove2Me formalization.