Lemma 11, p. 803 — a distance function meeting the weighted distance constraint yields a cut of weighted ratio cost ≤ 36W log p
ProvedLeightonRao.Product.lemma_11approximationmulticommodity-flowp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1sparsest-cut
Let be a connected capacitated network on , let be a PMFP node weighting with and , and let be a distance function with total weight satisfying the weighted distance constraint
Then there is a cut with , and
Combined with LP duality ( for an optimal distance function) this gives , the lower half of Theorem 7.
Formalization Note The page states . The constant bounds both branches of the proof: Corollary 9's and Lemma 10's , since for . The normalization is the standing assumption of §2.3; connectivity makes graph distances meaningful.
Preamble
import Mathlib import Definitions.Def_LeightonRao_Product_Setting
Formal statement
namespace LeightonRao.Product
theorem lemma_11 {V : Type} [Fintype V] [DecidableEq V] (N : Network V) (hconn : IsConnectedNet N)
(π : V → ℝ) (hπ : IsPMFPWeight π) (hp : 2 ≤ (support π).card) (d : V → V → ℝ)
(hd : IsDistanceFunction d) (hdc : SatisfiesPMFPConstraint N π d) :
∃ U : Finset V, 0 < piSum π U ∧ 0 < piSum π Uᶜ ∧
weightedRatio N π U ≤ 36 * totalWeight N d * Real.logb 2 ((support π).card : ℝ) := by sorry
end LeightonRao.Product
Source
Leighton and Rao, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, J. ACM 46 (1999), p. 803, Lemma 11
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.