Combining regional optimization tables returns a labeling of the unique global optimum
ProvedStableMSR.Recovery.Supplement.BinaryRecovery.Regional.regional_table_recoveryalgorithmsclusteringcomputational-complexity
On disjoint regions covering the input, assume every local row is feasible for its own region and contains the restricted optimum at its true count. Then the exact-count dynamic program reconstructs the global unique optimum. All returned blocks use the original point indices.
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.regional_table_recovery (I : RationalInput) (hI : I.Valid) (O : Partition I.n)
(ho : UniqueOptimal I.dist Finset.univ I.k O) (ws : Pack)
(hc : Represents I.n Finset.univ ws) (g : Block → Table)
(hg : ∀ w∈ws, LocalTable I O w (g w)) :
∃ p∈assemble (fieldsOf I) (ws.map g),
(labelPack (fieldsOf I) p).length=I.n ∧
labelsPartition I.n I.k (labelPack (fieldsOf I) p)=O := 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