Theorem 2, p. 795 — for every uniform multicommodity flow problem, Ω(𝒮/log n) ≤ f ≤ 𝒮
ProvedLeightonRao.Uniform.theorem_2For a network on nodes, let be the max-flow and the min-cut of its uniform multicommodity flow problem (demand one between every pair of nodes). There is an absolute constant such that for every connected network on nodes
This is the approximate max-flow min-cut theorem for uniform demands: the min-cut can exceed the max-flow by at most a logarithmic factor, and the example of §2.1 (Theorem 1) shows the factor is attained.
Formalization Note is rendered with one constant chosen before the network, uniform over all vertex types and capacities. The proof in the paper gives . (footnote 3). Connectivity is the paper's standing assumption (p. 789) and is needed for a cut to exist. Uniform demands are two ordered commodities of demand per pair (footnote 2).
import Definitions.Def_LeightonRao_Uniform_Flow set_option autoImplicit false open scoped BigOperators
namespace LeightonRao.Uniform
/-- Theorem 2, p. 795. The Ω constant is independent of the network and its size. -/
theorem theorem_2 :
∃ c : ℝ, 0 < c ∧
∀ {V : Type} [Fintype V] [DecidableEq V] (N : Network V),
2 ≤ Fintype.card V → IsConnectedNet N →
c * minCut N / Real.logb 2 (Fintype.card V : ℝ) ≤
maxFlow N uniformDemand ∧
maxFlow N uniformDemand ≤ minCut N := by sorry
end LeightonRao.Uniform
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.