Binary regional tables and exact-count dynamic programming for sum-of-radii clustering
DefinitionStableMSR_Recovery_Supplement_RegionalTablesalgorithmsclusteringdynamic-programming
Configurations list a radius and disjoint regions. Each local row lists candidate partitions into point blocks. The dynamic program retains a cheapest witness for each attainable cluster count. The full Cartesian product is defined solely to express the correctness invariant.
Definition code
import Definitions.Def_StableMSR_Recovery_Supplement_LargeBallSearch
set_option autoImplicit false
namespace StableMSR.Recovery.Supplement.BinaryRecovery.Regional
open BinaryVerifier
abbrev Block := List ℕ
abbrev Pack := List Block
abbrev Table := List Pack
abbrev Scenario := ℚ × Pack
abbrev RegionInput := Input × ℚ × Block
def rawBlock (n : ℕ) (w : Block) : Cluster n :=
Finset.univ.filter (fun x => x.val ∈ w)
def rawParts (n : ℕ) (p : Pack) : Partition n := (p.map (rawBlock n)).toFinset
def InRange (n : ℕ) (p : Pack) : Prop := ∀ w∈p, ∀ i∈w, i<n
def Represents (n : ℕ) (W : Cluster n) (p : Pack) : Prop :=
InRange n p ∧ Feasible W p.length (rawParts n p)
def Aligned {n : ℕ} (O : Partition n) (W : Cluster n) : Prop :=
W = (restrictPartition O W).biUnion id
def GoodScenario (I : RationalInput) (O : Partition I.n) (γ : ℚ) (s : Scenario) : Prop :=
(s.1 : ℝ) = largestRadius I.dist O ∧ Represents I.n Finset.univ s.2 ∧
∀ w∈s.2, Aligned O (rawBlock I.n w) ∧
diameter I.dist (rawBlock I.n w) ≤ densityScale I.dist O ((γ:ℝ)-1)
def LocalTable (I : RationalInput) (O : Partition I.n) (w : Block) (row : Table) : Prop :=
(∀ p∈row, Represents I.n (rawBlock I.n w) p) ∧
∃ p∈row, rawParts I.n p=restrictPartition O (rawBlock I.n w)
def weight (a : Input) (p : Pack) : ℚ :=
(p.map (blockRadius a.1 a.2.2)).sum
def counts (a : Input) : List ℕ := 0 :: (points a).map (·+1)
def cross (row acc : Table) : Table := row.flatMap fun p => acc.map (p++·)
def trim (a : Input) (ps : Table) : Table :=
(counts a).flatMap fun j =>
let good := ps.filter (fun p => decide (p.length=j))
(good.filter (fun p => good.all (fun q => decide (weight a p ≤ weight a q)))).take 1
def step (a : Input) (row acc : Table) : Table := trim a (cross row acc)
def assemble (a : Input) (rows : List Table) : Table := rows.foldr (step a) [[]]
def choices (rows : List Table) : Table := rows.foldr cross [[]]
def labelPack (a : Input) (p : Pack) : List ℕ :=
fromRelation (points a) (fun i j => p.any fun w => w.contains i && w.contains j)
def candidates (F : Input → List Scenario) (G : RegionInput → Table) (a : Input) : List (List ℕ) :=
(F a).flatMap fun s => (assemble a (s.2.map (fun w => G (a,s.1,w)))).map (labelPack a)
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