Residual-ball contributions are clique factors of the 8R interaction graph
ProvedStableMSR.Recovery.Supplement.BinaryRecovery.Regional.priority_factors_are_localalgorithmsclusteringdynamic-programming
All possible owners able to affect the residual of a ball centered at c lie within 4R of c. They form a clique in the 8R interaction graph. Agreement on those owner choices preserves the residual for every assignment, including overlapping candidate choices.
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_factors_are_local (γ : ℚ) (hg : 1<γ) (hu : γ<2) (I : RationalInput) (hv : I.Valid)
(R : ℚ) (w : Block) (rp : 0<R) (t : ℕ)
(tw : RobertsonSeymour1986.GM5.TreewidthLE (interactionGraph I.dist (R:ℝ) (rawBlock I.n w)) t) :
let z : RegionInput := (fieldsOf I,R,w)
ScopeWidth (netKeys z) ((featureIds z).map (featureScope z)) t ∧
∀i∈featureIds z, DependsOn (netKeys z) (featureScope z i) (featureOut γ z i) := 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.