Exact minimum-cost selection from a polynomial list of clustering candidates
ProvedStableMSR.Recovery.Supplement.BinaryRecovery.candidate_selectionalgorithmsclusteringcomputational-complexity
Filtering for feasible label vectors and taking a minimum of the exact rational costs is polynomial. On a stable input, whenever the list contains a labeling of the stable optimum, the selected candidate encodes that same partition.
Preamble
import Definitions.Def_StableMSR_Recovery_Supplement_CandidateSelection 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.candidate_selection (F : Input → List (List ℕ)) (hp : Poly F) : Poly (fun a => select a (F a)) ∧ ∀ γ : ℚ, ContainsStable F γ → 1 ≤ γ → Recovers (fun a => select a (F a)) γ := by sorry
Source
S. Ravichandran and L. Reyzin, Exact Sum-of-Radii Clustering under Any Constant Stability, Section 3 and Appendix C.4. https://arxiv.org/abs/2611.03547 . The common-radius two-edge criterion is deduced from the published center and intercluster separation statements.