Deterministic zero-split seed when every maximum-radius component fits the density scale
ProvedStableMSR.Recovery.Supplement.BinaryRecovery.Regional.bounded_component_seedalgorithmsclusteringcomputational-complexity
Guess the true largest radius among input distances and compute its threshold components. Every optimal block lies in one such component. If all components have diameter within the density scale, their partition is a good deterministic seed with exactly zero split blocks. No restriction on the number of clusters or components is needed.
Preamble
import Definitions.Def_StableMSR_Recovery_Supplement_ThresholdComponents 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_component_seed :
Poly componentSeeds ∧
∀ (γ : ℚ) (_ : 1<γ) (I : RationalInput) (_ : I.Valid) (O : Partition I.n),
Stable I.dist I.k (γ:ℝ) O →
2*largestRadius I.dist O ≤ densityScale I.dist O ((γ:ℝ)-1) →
¬Wide I O γ → ∃ s∈componentSeeds (fieldsOf I), Seed I O γ 0 s := 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