Priority completion always returns a genuine partition and its exact encoded cost
ProvedStableMSR.Recovery.Supplement.BinaryRecovery.Regional.priority_partition_soundalgorithmsclusteringdynamic-programming
Regardless of overlaps or the owner choices, each regional point is claimed by its first covering offer. Its own fallback ball guarantees coverage. The nonempty fibers give a disjoint partition and its binary cost is the actual sum of the radii of the residual point sets.
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_partition_sound (γ : ℚ) (hg : 1<γ) (I : RationalInput) (hv : I.Valid)
(R : ℚ) (w : Block) (rp : 0<R) (s : Plan) :
let z : RegionInput := (fieldsOf I,R,w)
let p := priorityPack γ z s
Represents I.n (rawBlock I.n w) p ∧ (weight (fieldsOf I) p:ℝ)=cost I.dist (rawParts I.n 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.