Algorithm 1, Branch A: bounded candidate enumeration and exact recovery
ProvedStableMSR.Recovery.few_large_cluster_recoveryLet be a finite metric on points, let , and fix and an integer . Construct the Branch A output family by enumerating all input-distance radius guesses, all pairwise disjoint families of at most candidate ball representations, and their global-component completions. This explicit family has at most
outputs. Starting from any feasible exact- partition, the feasibility-checked minimum-cost scan always returns a feasible exact- partition.
If the instance has a -stable optimum with at most clusters of radius at least , where is its largest radius, the scan returns exactly .
The theorem establishes correctness and the candidate-family size for the bounded-enumeration branch. The accompanying proof supplies an equivalent enumeration by length- tuples of candidate representations and blanks, so the family need not be generated by scanning an unbounded powerset. The result is a finite-algorithm specification; the full interpreter runtime and the many-large-clusters branch remain separate obligations.
import Definitions.Def_StableMSR_Recovery_FewBranch set_option autoImplicit false open scoped Classical
namespace StableMSR.Recovery
theorem few_large_cluster_recovery {n : ℕ} (d : Point n → Point n → ℝ)
(hd : IsMetricArray d) (k : ℕ) (hk : 1 ≤ k ∧ k ≤ n)
(γ : ℝ) (hγ : 1 < γ ∧ γ < 2) (hkn : k < n) (budget : ℕ)
(initial : Partition n) (hi : Feasible Finset.univ k initial) :
(CandidateAux.fewOutputs d γ budget).card ≤ n ^ 2 * (n ^ 2 + 1) ^ budget ∧
Feasible Finset.univ k
(CandidateAux.select d k initial (CandidateAux.fewOutputs d γ budget).toList) ∧
∀ O : Partition n, Stable d k γ O →
(largeClusters d O (γ - 1)).card ≤ budget →
CandidateAux.select d k initial (CandidateAux.fewOutputs d γ budget).toList = O := by sorry
end StableMSR.Recovery