Factorized distance-oracle regional menus for the many-large-cluster regime
OpenStableMSR.Recovery.RegionalBallDP.dense_factorized_regional_catalogalgorithmsclusteringdynamic-programmingformal-verification
Generate a polynomial-size family of regional choices on the real-distance machine within the paper’s parameter envelope. In each promised stable instance, some full-width terminal accepts only covering, distinct-center assemblies and has one assembly of cost at most the optimal cost. Its alternatives may be emitted separately for each prefix count.
Preamble
import Definitions.Def_StableMSR_RegionalBallDP open StableMSR.Recovery StableMSR.Recovery.Compiler StableMSR.Recovery.OracleQueries open StableMSR.Recovery.BallCoverCatalog StableMSR.Recovery.CartesianBallRows StableMSR.Recovery.FewBallRows open StableMSR.Recovery.RegionalBallDP open scoped Classical set_option autoImplicit false set_option maxHeartbeats 2200000 set_option maxRecDepth 12000
Formal statement
theorem StableMSR.Recovery.RegionalBallDP.dense_factorized_regional_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 → regionalSpec e a b cmd n k d := by
sorrySource
Exact Sum-of-Radii Clustering under Any Constant Stability, arXiv:2611.03547, Algorithm 1, equation (2), and Appendix A.4–A.6. Real-distance oracle implementation and witness reconstruction for the Prove2Me recovery mission.