Construct recovery certificates when the cluster count exceeds the few-cluster bound
OpenStableMSR.Recovery.CartesianBallRows.interior_ball_cover_catalogalgorithmsclustering
Construct a uniformly bounded generator of center/witness rows for the remaining parameter regime. The input cluster count is strictly between the explicit few-cluster bound and n. On stable instances at least one row must cover the metric with distinct centers at total nominal cost at most the optimum.
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.interior_ball_cover_catalog : ∃a b : ℕ,0 < a ∧ 0 < b ∧ ∀e : ℚ,0 < e → e < 1 →
∃cmd : Cmd,∀ (n k : ℕ) (d : Point n→Point n→ℝ),
1 ≤ k → k < n → fewBound (e:ℝ) < k → IsMetricArray d → runSpec e a b cmd n k d := 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.