Cost of the supplied partition and canonical competitor after hub inflation
ProvedStableMSR.Recovery.Supplement.hub_inflation_costsIn the hub-and-dummy construction for Proposition C.2, let be the original hub-to-source distance and let be the source diameter. Write for the minimum cost of an exact- partition of the source and for the dummy-to-dummy distance. Assume and . For any , replace all hub-to-source distances by in both directions.
The supplied partition then has cost . The source-plus-hub cluster has eccentricity at every center, and each dummy singleton has radius zero. A distinct exact- partition has cost . It consists of an optimal exact- source partition, the hub singleton, and all dummy points together. Each of those clusters uses only unchanged distances.
Preamble
import Definitions.Def_StableMSR_Recovery_Supplement_Hub set_option autoImplicit false open scoped Classical
Formal statement
namespace StableMSR.Recovery.Supplement
theorem hub_inflation_costs {n k : ℕ} (d : Point n → Point n → ℝ) (γ τ s : ℝ)
(hk : 1 ≤ k) (hkn : k ≤ n) (hd : IsMetricArray d)
(hD : diameter d Finset.univ ≤ hubRadius d γ τ)
(hs : hubRadius d γ τ ≤ s) (hδ : 0 ≤ dummyDistance d γ τ) :
let dp := hubDistance d k γ τ
let p := fun (x y : Point (n + k + 2)) =>
if (x.val = n ∧ y.val < n) ∨ (y.val = n ∧ x.val < n) then s else dp x y
cost p (suppliedPartition n k) = s ∧
∃ Q, Feasible Finset.univ (k + 2) Q ∧ Q ≠ suppliedPartition n k ∧
cost p Q = dummyDistance d γ τ + optimumValue d k := by sorry
end StableMSR.Recovery.Supplement
Source
Shyam Ravichandran, Lev Reyzin, STOC 2027 submission #1010 (October 2026), Proposition C.2, p. 25; PDF SHA256 8bb34b0b6d31458fe6fc0848c1fc82a6083f3e9ae672e748d24cf82d5289e53e