Polynomial-bit local optimization for ball candidates and optional components at bounded treewidth
ProvedStableMSR.Recovery.Supplement.BinaryRecovery.Regional.bounded_width_binary_optimizeralgorithmsclusteringcomputational-complexity
For fixed width and candidate capacity, compute feasible regional witnesses that, at every feasible count, cost no more than any partition represented by the large balls and eligible optional components. The input promise concerns only the interaction graph. Stability, the unknown optimum, and the density-scale bound are absent from the optimization specification. Use the local candidate constraints, clique bags, and count-indexed bounded-treewidth recurrence in A.4–A.6.
Preamble
import Definitions.Def_RobertsonSeymour1986_GM5_TreewidthLE 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.bounded_width_binary_optimizer (γ : ℚ) (hg : 1<γ) (hu : γ<2) (h t : ℕ) :
∃ G : RegionInput → Table, Poly G ∧
∀ (I : RationalInput) (_ : I.Valid) (R : ℚ) (w : Block), 0<R →
(∀ i∈w,i<I.n) → (rawBlock I.n w).Nonempty →
RobertsonSeymour1986.GM5.TreewidthLE (interactionGraph I.dist (R:ℝ) (rawBlock I.n w)) t →
DominatingRow I γ (R:ℝ) (rawBlock I.n w) h (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