Every feasible partition has an exact-cost ball-cover certificate
ProvedStableMSR.Recovery.CartesianBallRows.cartesian_rows_certify_partitionsalgorithmsclustering
Index the blocks, choose a center of minimum eccentricity in each, and choose a farthest point attaining that radius. Their digits form a row that covers all points and has precisely the partition cost.
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.cartesian_rows_certify_partitions (x : World) (hn : 0 < x.n) (h : pairs x) :
endpoints x ∧ ∀O,Feasible Finset.univ x.k O →
∃r < x.rows,good x r ∧ score x r=cost x.dist 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.