A covering ball certificate suffices for unique optimal recovery
ProvedStableMSR.Recovery.BallCoverCatalog.cheapest_cover_recoversalgorithmsclustering
Choose the lowest-score valid row, assign centers to their own clusters, and assign every other point to its first covering ball. The decoded partition is feasible and its actual cost is bounded by the row score. A stable optimum is recovered whenever a row has score at most its cost.
Preamble
import Definitions.Def_StableMSR_BallCoverCatalog open StableMSR.Recovery StableMSR.Recovery.Compiler StableMSR.Recovery.OracleQueries open Polynomial open StableMSR.Recovery.BallCoverCatalog
Formal statement
theorem StableMSR.Recovery.BallCoverCatalog.cheapest_cover_recovers (x : World) (s : MinSumFPT.State) (hk : 1 ≤ x.k) (hn : x.k ≤ x.n)
(hm : IsMetricArray x.dist) (he : endpoints x)
(hs : ∀i < x.n,s.imem (-1-(i:ℤ))=output x i) :
ValidLabels x.n x.k s ∧ ∀ (γ : ℝ),1 ≤ γ → ∀ O,Stable x.dist x.k γ O →
(∃r < x.rows,good x r ∧ score x r ≤ cost x.dist O) → outputPartition x.n x.k s=O := 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.