p. 804 — directed weak duality: a concurrent flow of value λ satisfies λ|U||Ū| ≤ C(U, Ū)
ProvedLeightonRao.Directed.weak_dualitydirected-graphmulticommodity-flowp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1weak-duality
Let be a directed network on and let be a concurrent flow of value for the directed uniform multicommodity flow problem (demand from to for every ordered pair ). Then for every nonempty proper subset ,
where is the total capacity of the edges directed from to .
Taking the supremum over flows and the minimum over cuts gives the upper bound of Theorem 12, which the paper says "follows immediately from the definitions".
Formalization Note Each of the commodities with , must cross the cut in the forward direction. No connectivity assumption is needed.
Preamble
import Mathlib import Definitions.Def_LeightonRao_Directed_Setting
Formal statement
namespace LeightonRao.Directed
/-- Leighton–Rao, p. 804: "The fact that f ≤ 𝒮 follows immediately from the definitions." For every
directed concurrent flow of value `lam` for the directed UMFP and every nonempty proper `U`,
`lam · |U| |Ū| ≤ C(U, Ū)`. -/
theorem weak_duality {V : Type} [Fintype V] [DecidableEq V] (N : DiNetwork V)
(f : V → V → V → V → ℝ) (lam : ℝ) (hf : IsDiConcurrentFlow N diDemand f lam)
(U : Finset V) (hU : U.Nonempty) (hUc : Uᶜ.Nonempty) :
lam * ((U.card : ℝ) * (Uᶜ.card : ℝ)) ≤ diCutCap N U := by sorry
end LeightonRao.Directed
Source
Leighton and Rao, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, J. ACM 46 (1999), p. 804, §2.4, sentence after Theorem 12 (f ≤ 𝒮)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.