A linear-time singleton cover for the diagonal case
ProvedStableMSR.Recovery.CartesianBallRows.singleton_cover_machinealgorithmsclustering
For k=n, emit the single row whose jth center and witness are both j. Its balls cover the input and their total radius is zero. The loop takes linear charged 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.singleton_cover_machine : ∃a : ℕ,0 < a ∧ ∃cmd : Cmd,
∀ (n : ℕ) (d : Point n→Point n→ℝ),1 ≤ n → IsMetricArray d →
∃s z,Executes d cmd (initialStore n n) s z ∧ z ≤ a*n ∧
let x := worldOf n 1 d s
Ready x s ∧ endpoints x ∧ ∀O,Feasible Finset.univ n O →
∃r < 1,good x r ∧ score x r ≤ cost d 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.