Every modeled regional partition occurs among priority-ball assignments
ProvedStableMSR.Recovery.Supplement.BinaryRecovery.Regional.priority_assignments_represent_modelsalgorithmsclusteringdynamic-programming
Assign every modeled large ball to a covering net vertex. Such a ball lies in the owner’s 3R-ball, so the model permits at most h per owner. Large balls take their disjoint blocks first. Each remaining small block is a whole global threshold component, has diameter below the threshold, and is recovered by its first fallback center.
Preamble
import Definitions.Def_StableMSR_Recovery_Supplement_PriorityRegions import Definitions.Def_StableMSR_Recovery_Supplement_RegionalModel open StableMSR.Recovery StableMSR.Recovery.Supplement StableMSR.Recovery.Supplement.BinaryRecovery open StableMSR.Recovery.Supplement.BinaryRecovery.Regional
Formal statement
theorem StableMSR.Recovery.Supplement.BinaryRecovery.Regional.priority_assignments_represent_models (γ : ℚ) (hg : 1<γ) (hu : γ<2) (I : RationalInput) (hv : I.Valid)
(R : ℚ) (w : Block) (rp : 0<R) (h : ℕ) (P : Partition I.n)
(model : LocalModel I γ (R:ℝ) (rawBlock I.n w) h P) :
let z : RegionInput := (fieldsOf I,R,w)
∃ s : Plan, AllowedPlan (netKeys z) (tuples (ballCodes z.1) h) s ∧
rawParts I.n (priorityPack γ z s)=P := by
sorry
Source
S. Ravichandran and L. Reyzin, Exact Sum-of-Radii Clustering under Any Constant Stability, Proposition 4.2 and Appendices A.4 and A.6, https://arxiv.org/abs/2611.03547. The priority-ball construction is an alternative implementation of the regional optimization.