Local candidate representation and cost dominance at prescribed counts
DefinitionStableMSR_Recovery_Supplement_RegionalModelalgorithmsclusteringdynamic-programming
A regional partition is represented by isolated large balls and eligible small global components, with a per-owner packing bound. A regional table dominates all represented competitors at their own cluster counts.
Definition code
import Definitions.Def_StableMSR_Recovery_Supplement_RegionalTables
set_option autoImplicit false
namespace StableMSR.Recovery.Supplement.BinaryRecovery.Regional
noncomputable def LocalModel (I : RationalInput) (γ : ℚ) (R : ℝ) (W : Cluster I.n) (h : ℕ)
(P : Partition I.n) : Prop := by
classical
let b := ((γ:ℝ)-1)*R/4
exact Feasible W P.card P ∧ ∃ L⊆P,
(∀ C∈L, b≤radius I.dist C ∧ radius I.dist C≤R ∧
∃ c z : Fin I.n, OptimalCenter I.dist C c ∧ z∈C ∧ I.dist c z=radius I.dist C ∧
C=ball I.dist c (radius I.dist C) ∧ C=ball I.dist c ((γ:ℝ)*radius I.dist C)) ∧
(∀ C∈P, C∉L → C∈components I.dist (2*b) Finset.univ ∧ radius I.dist C<b) ∧
∀ v : Fin I.n, (L.filter (fun C => C⊆ball I.dist v (3*R))).card≤h
def DominatingRow (I : RationalInput) (γ : ℚ) (R : ℝ) (W : Cluster I.n) (h : ℕ) (row : Table) : Prop :=
(∀ p∈row, Represents I.n W p) ∧ ∀ P : Partition I.n, LocalModel I γ R W h P →
∃ p∈row, p.length=P.card ∧ cost I.dist (rawParts I.n p)≤cost I.dist P
end StableMSR.Recovery.Supplement.BinaryRecovery.Regional
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