§1.2, pp. 789–790 — PMFP weak duality: every concurrent flow value f satisfies f·π(U)π(Ū) ≤ C(U, Ū)
ProvedLeightonRao.Product.weak_dualitymax-flow-min-cutmulticommodity-flowp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1weak-duality
Let be a capacitated network on a finite vertex set , let be a node weighting, and consider the product multicommodity flow problem in which each ordered pair is a commodity with demand . If a concurrent flow of value exists, then for every cut with and ,
The demand separated by is , so this is the paper's observation that , i.e. the max-flow is at most the min-cut. It gives the upper half of Theorem 7.
Formalization Note The paper states the observation for an arbitrary multicommodity flow problem; here it is specialized to the product demands of §2.3.
Preamble
import Mathlib import Definitions.Def_LeightonRao_Product_Setting
Formal statement
namespace LeightonRao.Product
theorem weak_duality {V : Type} [Fintype V] [DecidableEq V] (N : Network V) (π : V → ℝ)
(f : V → V → V → V → ℝ) (lam : ℝ) (hf : IsConcurrentFlow N (productDemand π) f lam)
(U : Finset V) (hU : 0 < piSum π U) (hUc : 0 < piSum π Uᶜ) :
lam * (piSum π U * piSum π Uᶜ) ≤ cutCap N U := 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), pp. 789–790, §1.2, paragraph after the min-cut definition (max-flow upper bounded by min-cut), applied to the PMFP of §2.3, p. 801
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.