Polynomial-bit evaluation of the domain, scopes, and residual-ball contributions
ProvedStableMSR.Recovery.Supplement.BinaryRecovery.Regional.priority_factor_bit_programsalgorithmsclusteringdynamic-programming
With fixed capacity, enumerate owner options by tuples of at most h center/farthest pairs. Every feature, scope, priority-fiber calculation, and residual radius is computed on polynomially many encoded points and exact rationals.
Preamble
import Definitions.Def_QuantumMaxCutFiniteNumericRuntime import Definitions.Def_StableMSR_Recovery_Supplement_PriorityRegions import Definitions.Def_StableMSR_Recovery_Supplement_RegionalModel open StableMSR.Recovery StableMSR.Recovery.Supplement StableMSR.Recovery.Supplement.BinaryRecovery open StableMSR.Recovery.Supplement.BinaryRecovery.Regional open OAI.MetricKMedian.Binary.Automatic
Formal statement
theorem StableMSR.Recovery.Supplement.BinaryRecovery.Regional.priority_factor_bit_programs (γ : ℚ) (h : ℕ) :
Poly featureIds ∧ Poly (fun z : RegionInput => tuples (ballCodes z.1) h) ∧
Poly (fun z : RegionInput×ℕ => featureScope z.1 z.2) ∧
Poly (fun z : (RegionInput×ℕ)×Plan => featureOut γ z.1.1 z.1.2 z.2) ∧
Poly (fun z : RegionInput×Block => BinaryVerifier.blockRadius z.1.1.1 z.1.1.2.2 z.2) := by
sorry
Source
S. Ravichandran and L. Reyzin, Exact Sum-of-Radii Clustering under Any Constant Stability, Proposition 4.2 and Appendices A.4 and A.6, https://arxiv.org/abs/2611.03547. The priority-ball construction is an alternative implementation of the regional optimization.