Selecting feasible rational clustering candidates and enumerating two-edge threshold labels
DefinitionStableMSR_Recovery_Supplement_CandidateSelectionalgorithmsclusteringcomputational-complexity
A generic minimum-cost selection over a polynomial candidate list, and a concrete candidate list obtained by enumerating the rational input distances and grouping by two-edge threshold reachability. All loops are bounded by parsed input or lists.
Definition code
import Definitions.Def_StableMSR_Recovery_Supplement_BinaryRecovery
set_option autoImplicit false
namespace StableMSR.Recovery.Supplement.BinaryRecovery
open BinaryVerifier
/-- The search list needs to contain a labeling of each stable solution. -/
def ContainsStable (F : Input → List (List ℕ)) (γ : ℚ) : Prop :=
∀ I : RationalInput, I.Valid → ∀ O : Partition I.n, Stable I.dist I.k γ O →
∃ l ∈ F (fieldsOf I), l.length = I.n ∧ labelsPartition I.n I.k l = O
def eligible (a : Input) (l : List ℕ) : Bool :=
decide (l.length=a.1) && labelsOK a.2.1 l
/-- Compute a feasible minimum among the listed labelings, using exact rational costs. -/
def select (a : Input) (ls : List (List ℕ)) : List ℕ :=
let good := ls.filter (eligible a)
let val := total a.1 a.2.1 a.2.2
(good.filter (fun x => good.all (fun y => decide (val x ≤ val y)))).head?.getD []
/-- The enumeration length is bounded by the actual table length even on malformed data. -/
def points (a : Input) : List ℕ := (List.range a.2.2.length).take a.1
def twoHop (a : Input) (t : ℚ) (i j : ℕ) : Bool :=
(points a).any fun z => decide (distAt a.1 a.2.2 i z ≤ t) && decide (distAt a.1 a.2.2 z j ≤ t)
def keys (a : Input) (t : ℚ) : List ℕ :=
(points a).map fun i => ((points a).filter (twoHop a t i)).head?.getD 0
def compact (ps ks : List ℕ) : List ℕ :=
let palette := ps.filter (fun j => ks.contains j)
ks.map (fun i => palette.idxOf i)
def thresholdCandidates (a : Input) : List (List ℕ) := a.2.2.map fun t => compact (points a) (keys a t)
end StableMSR.Recovery.Supplement.BinaryRecovery
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.