Stable local optima have a candidate representation with the exact per-owner packing bound
ProvedStableMSR.Recovery.Supplement.BinaryRecovery.Regional.stable_local_representationalgorithmsclusteringcomputational-complexity
On every nonempty aligned region, the restriction of a stable optimum is a unique optimum. Each large block is an isolated candidate ball with an input center and farthest point, and each remaining block is an eligible global small component. For every input point v, at most floor(12/(γ−1)) of the selected large blocks lie wholly in its radius-3R ball. The representation theorem needs no diameter assumption.
Preamble
import Definitions.Def_StableMSR_Recovery_Supplement_RegionalModel import Definitions.Def_StableMSR_Recovery_Supplement_Partitions import Definitions.Def_QuantumMaxCutFiniteNumericRuntime open OAI.MetricKMedian.Binary.Automatic open StableMSR.Recovery StableMSR.Recovery.Supplement StableMSR.Recovery.Supplement.BinaryRecovery open StableMSR.Recovery.Supplement.BinaryRecovery.Regional
Formal statement
theorem StableMSR.Recovery.Supplement.BinaryRecovery.Regional.stable_local_representation (γ : ℚ) (hg : 1<γ) (hu : γ<2)
(I : RationalInput) (hv : I.Valid) (O : Partition I.n) (ho : Stable I.dist I.k (γ:ℝ) O) (kn : I.k<I.n)
(W : Cluster I.n) (hne : W.Nonempty) (ha : StableMSR.Recovery.Aligned O W) :
let P := restrictPartition O W
0 < largestRadius I.dist O ∧ UniqueOptimal I.dist W P.card P ∧
LocalModel I γ (largestRadius I.dist O) W (ownerBound ((γ:ℝ)-1)) P := by
sorry
Source
S. Ravichandran and L. Reyzin, Exact Sum-of-Radii Clustering under Any Constant Stability, Section 4.1 equation (2), Proposition 4.2 and Appendices A.4–A.6. https://arxiv.org/abs/2611.03547