Bit-polynomial repair of any partition that splits at most a fixed number of stable blocks
ProvedStableMSR.Recovery.Supplement.BinaryRecovery.Regional.bounded_split_repairalgorithmsclusteringcomputational-complexity
For any polynomial input list of regional seeds, the explicit repair algorithm is polynomial and converts any seed cutting at most h optimal blocks into at least one aligned bounded-diameter partition in its output list. This theorem is independent of how the seed family is produced.
Preamble
import Definitions.Def_StableMSR_Recovery_Supplement_RegionRepair 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_split_repair (γ : ℚ) (hγ : 1<γ) (h : ℕ) (F : Input→List Scenario) (hp : Poly F) :
Poly (repairs h F) ∧ ∀ (I : RationalInput) (_ : I.Valid) (O : Partition I.n),
Stable I.dist I.k (γ:ℝ) O → ∀ s∈F (fieldsOf I), Seed I O γ h s →
∃ t∈repairs h F (fieldsOf I), GoodScenario I O γ t := 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