The regional dynamic program retains an optimal witness for every attainable count
ProvedStableMSR.Recovery.Supplement.BinaryRecovery.Regional.exact_count_dominancealgorithmsclusteringcomputational-complexity
Every retained witness comes from the regional choices. At each attainable cluster count covered by the prefix of the cap, at least one retained witness has minimum exact rational cost among all compatible choices. This proves equation (2) with reconstruction.
Preamble
import Definitions.Def_StableMSR_Recovery_Supplement_RegionalTables 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.exact_count_dominance (a : Input) (rows : List Table) :
(∀ p∈assemble a rows, p∈choices rows) ∧
∀ p∈choices rows, (∀ j≤p.length, j∈counts a) →
∃ q∈assemble a rows, q.length=p.length ∧ weight a q ≤ weight a 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