Binary local optimization tables on aligned small-diameter regions
ProvedStableMSR.Recovery.Supplement.BinaryRecovery.Regional.aligned_region_table_programalgorithmsclusteringcomputational-complexity
At the true largest radius, solve a single aligned region of bounded diameter using the original global distances. The local table contains only feasible regional partitions and includes the restriction of the optimum. Proposition 4.2 and Appendix A.6 supply the bounded-treewidth construction. This statement requires no interaction between regions.
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.aligned_region_table_program (γ : ℚ) (hγ : 1<γ) (hlt : γ<2) :
∃ G : RegionInput → Table, Poly G ∧
∀ (I : RationalInput) (_ : I.Valid) (O : Partition I.n),
Stable I.dist I.k (γ:ℝ) O → I.k<I.n → ∀ (R : ℚ) (w : Block),
(R:ℝ)=largestRadius I.dist O → (∀ i∈w,i<I.n) →
Aligned O (rawBlock I.n w) →
diameter I.dist (rawBlock I.n w) ≤ densityScale I.dist O ((γ:ℝ)-1) →
LocalTable I O w (G (fieldsOf I,R,w)) := 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