Lemma 6, p. 800 — a distance function satisfying (5) yields a cut of ratio cost ≤ 36W log n
ProvedLeightonRao.Uniform.lemma_6graph-cutlp-dualityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1sparsest-cut
Let be a connected network on nodes and a distance function with total weight that satisfies the distance constraint . Then there is a nonempty proper subset with
Combined with the existence of a distance function with (LP duality), this gives the lower half of Theorem 2.
Formalization Note The page states "ratio cost ". The constant comes from the proof on p. 800: it takes Corollary 4's bound or Lemma 5's bound , and since for . Connectivity is the paper's standing assumption (p. 789).
Preamble
import Definitions.Def_LeightonRao_Uniform_Dual set_option autoImplicit false open scoped BigOperators
Formal statement
namespace LeightonRao.Uniform
/-- Lemma 6, p. 800, with the factor `36` from Corollary 4 and Lemma 5. -/
theorem lemma_6 {V : Type} [Fintype V] [DecidableEq V]
(N : Network V) (hn : 2 ≤ Fintype.card V) (hconn : IsConnectedNet N)
(d : V → V → ℝ) (hd : IsDistanceFunction d)
(hconstraint : SatisfiesDistanceConstraint N d) :
∃ U : Finset V, U.Nonempty ∧ Uᶜ.Nonempty ∧
ratioCost N U ≤ 36 * totalWeight N d * Real.logb 2 (Fintype.card V : ℝ) := by sorry
end LeightonRao.Uniform
Source
Leighton and Rao, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, J. ACM 46 (1999), p. 800, Lemma 6 (constant from Corollary 4 and Lemma 5)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.