Exact sum-of-radii optimization in n to the O(k) charged time
ProvedStableMSR.Recovery.CartesianBallRows.exact_recovery_in_dimension_kalgorithmsclustering
One finite deterministic distance-oracle program outputs a globally optimal exact-k partition on every finite metric input without any stability condition. It enumerates center and boundary-point pairs and minimizes over covering rows in charged n^{O(k)} time.
Preamble
import Definitions.Def_StableMSR_CartesianBallRows open StableMSR.Recovery StableMSR.Recovery.Compiler StableMSR.Recovery.OracleQueries StableMSR.Recovery.BallCoverCatalog StableMSR.Recovery.CartesianBallRows
Formal statement
theorem StableMSR.Recovery.CartesianBallRows.exact_recovery_in_dimension_k : ∃a b : ℕ,0 < a ∧ 0 < b ∧ ∃P : MinSumFPT.Program,DeterministicProgram P ∧
∀(n k : ℕ) (d : Point n→Point n→ℝ),1 ≤ k → k ≤ n → IsMetricArray d →
∃t ≤ a*n^(b*(k+1)),
let s := execute P n k d t
s.halted=true ∧ s.work ≤ a*n^(b*(k+1)) ∧ ValidLabels n k s ∧
Optimal d Finset.univ k (outputPartition n k s) := by
sorry
Source
Shyam Ravichandran and Lev Reyzin, Exact Sum-of-Radii Clustering under Any Constant Stability, arXiv:2611.03547, Algorithm 1 and Theorem 1.1. Finite deterministic RAM implementation and ball-cover certification.