Bit-polynomial recovery candidates for every stable instance with boundedly many large clusters
ProvedStableMSR.Recovery.Supplement.BinaryRecovery.few_large_binary_candidatesalgorithmsclusteringcomputational-complexity
A fully specified polynomial bit program enumerates the branches with at most a fixed number b of large clusters, for every stability factor between one and two. It covers k=n separately. The center and farthest-point guesses suffice for the large clusters; the diameter and component bounds identify all small blocks.
Preamble
import Definitions.Def_StableMSR_Recovery_Supplement_LargeBallSearch import Definitions.Def_QuantumMaxCutFiniteNumericRuntime open OAI.MetricKMedian.Binary.Automatic open StableMSR.Recovery StableMSR.Recovery.Supplement StableMSR.Recovery.Supplement.BinaryRecovery
Formal statement
theorem StableMSR.Recovery.Supplement.BinaryRecovery.few_large_binary_candidates (γ : ℚ) (hγ : 1<γ) (hγ' : γ<2) (b : ℕ) :
Poly (fewCandidates γ b) ∧ ∀ (I : RationalInput) (hI : I.Valid) (O : Partition I.n),
Stable I.dist I.k (γ:ℝ) O →
(I.k=I.n ∨ (largeClusters I.dist O ((γ:ℝ)-1)).card ≤ b) →
Appears (fewCandidates γ b) I O := by
sorry
Source
Ravichandran and Reyzin, Exact Sum-of-Radii Clustering under Any Constant Stability, Lemma 3.8, Section 4 Branch A and Branch B, Appendix A.5, and Proposition C.4. https://arxiv.org/abs/2611.03547