Theorem 7, pp. 801–802 — for every product multicommodity flow problem with k commodities, Ω(𝒮/log k) ≤ f ≤ 𝒮
ProvedLeightonRao.Product.theorem_7There is an absolute constant with the following property. Let be a connected capacitated network on a finite vertex set , and let be a node weighting with nodes of positive weight, normalized so that . Consider the product multicommodity flow problem in which every pair of nodes has demand ; it has commodities with nonzero demand. Let be its (concurrent) max-flow and
its min-cut. Then
The upper bound is weak duality; the lower bound says the gap between the multicommodity max-flow and min-cut for product demands is at most logarithmic in the number of commodities. The uniform problem () is the special case . The paper's proof gives .
Formalization Note The page's is one constant for all instances, so precedes every quantifier. For there is commodity and ; the bound is stated with , which changes nothing for . Demands are encoded on ordered pairs, each way (footnote 7). The min-cut ranges over cuts with . The normalization is the paper's "without loss of generality" of §2.3, kept as a hypothesis; connectivity is the standing assumption of p. 789.
import Mathlib import Definitions.Def_LeightonRao_Product_Setting
namespace LeightonRao.Product
theorem theorem_7 : ∃ c : ℝ, 0 < c ∧
∀ {V : Type} [Fintype V] [DecidableEq V] (N : Network V) (π : V → ℝ),
IsConnectedNet N → IsPMFPWeight π → 2 ≤ (support π).card →
c * pmfpMinCut N π / Real.logb 2 ((max (numCommodities π) 2 : ℕ) : ℝ) ≤
maxFlow N (productDemand π) ∧
maxFlow N (productDemand π) ≤ pmfpMinCut N π := by sorry
end LeightonRao.Product
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.