Runner-up lower bound for competitors that separate the dummy points from the source and hub
ProvedStableMSR.Recovery.Supplement.pure_competitor_lower_boundConsider the metric construction of Lemma C.1 with a nonempty source, one hub, and dummies, where . Assume the source diameter is smaller than the hub radius , and , the distance between distinct dummies. Let be a feasible exact- partition different from the supplied partition. Suppose each block lies wholly on the source-plus-hub side or wholly on the dummy side. Then
The counting argument forces a nonsingleton dummy block. When the hub is isolated, the source occupies at most blocks. When the hub shares a block with a source point, that block already contributes .
Preamble
import Definitions.Def_StableMSR_Recovery_Supplement_Hub set_option autoImplicit false open scoped Classical
Formal statement
namespace StableMSR.Recovery.Supplement
theorem pure_competitor_lower_bound {n k : ℕ} (d : Point n → Point n → ℝ) (γ τ : ℝ)
(hk : 1 ≤ k) (hkn : k ≤ n) (hd : IsMetricArray d)
(hD : diameter d Finset.univ < hubRadius d γ τ)
(hδ : hubRadius d γ τ < dummyDistance d γ τ)
(Q : Partition (n+k+2)) (hQ : Feasible Finset.univ (k+2) Q)
(hne : Q ≠ suppliedPartition n k)
(hpure : ∀ C ∈ Q, C ⊆ hubSource n k ∨ ∀ x ∈ C, n < x.val) :
dummyDistance d γ τ + optimumValue d k ≤ cost (hubDistance d k γ τ) Q := by sorry
end StableMSR.Recovery.Supplement
Source
Shyam Ravichandran and Lev Reyzin, Exact Sum-of-Radii Clustering under Any Constant Stability, arXiv:2611.03547, Appendix C, Lemma C.1, p. 24, unmixed-partition case.