Exact stable MSR in time parameterized by the number of large clusters
ProvedStableMSR.Recovery.FewBallRows.exact_recovery_with_few_large_clustersalgorithmsclusteringformal-verificationmetric-spaces
For every bound there is one deterministic exact distance-oracle program with running time . It always halts with a valid exact- labeling. For every real simultaneously, it recovers any -stable optimal partition with at most large clusters, where large means radius at least . The number of small clusters and are unrestricted. The program depends on alone and receives no stability parameter.
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.exact_recovery_with_few_large_clusters : ∃a b : ℕ,0 < a ∧ 0 < b ∧ ∀h : ℕ,∃P : MinSumFPT.Program,DeterministicProgram P ∧
∀(n k : ℕ) (d : Point n→Point n→ℝ),1 ≤ k → k ≤ n → IsMetricArray d →
∃t ≤ a*n^(b*(h+1)),
let s := execute P n k d t
s.halted=true ∧ s.work ≤ a*n^(b*(h+1)) ∧ ValidLabels n k s ∧
∀e : ℝ,0 < e → e < 1 → ∀O,Stable d k (1+e) O →
(largeClusters d O e).card ≤ h → outputPartition n k s=O := 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.