Turning an overlapping cover of whole clusters into a disjoint aligned regional partition
ProvedStableMSR.Recovery.Supplement.BinaryRecovery.Regional.normalize_aligned_coveralgorithmsclusteringcomputational-complexity
Assign a point to the index of its first containing member of a cover, then discard empty fibers. The resulting partition stays aligned with the optimum whenever cover membership is constant on each optimal block. Diameters do not increase, and overlapping or repeated cover members are allowed.
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.normalize_aligned_cover (I : RationalInput) (hv : I.Valid) (O : Partition I.n)
(ho : Feasible Finset.univ I.k O) (ps : Pack) (D : ℝ)
(cover : ∀ x : Fin I.n, ∃ w∈ps, x∈rawBlock I.n w)
(same : ∀ C∈O, ∀ x∈C, ∀ y∈C, ∀ w∈ps, x∈rawBlock I.n w ↔ y∈rawBlock I.n w)
(diam : ∀ w∈ps, ∀ x∈rawBlock I.n w, ∀ y∈rawBlock I.n w, I.dist x y≤D) :
Represents I.n Finset.univ (normalize (fieldsOf I) ps) ∧
∀ w∈normalize (fieldsOf I) ps, Aligned O (rawBlock I.n w) ∧ diameter I.dist (rawBlock I.n w)≤D := 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