§2.3, p. 802 with §2.2, p. 796 — PMFP LP duality: the minimum total weight of a distance function meeting the weighted distance constraint equals the max-flow
ProvedLeightonRao.Product.lp_dualityLet be a connected capacitated network on , and let be a PMFP node weighting with and at least nodes of positive weight. Let be the max-flow of the product multicommodity flow problem. Then
- every distance function satisfying the weighted distance constraint has total weight , and
- some distance function satisfying this constraint has total weight exactly
This is the linear-programming duality between the concurrent flow problem and its distance dual, which the paper cites (Chvátal, Iri, Shahrokhi–Matula) and uses with the PMFP distance constraint of p. 802. It is the step "" by which the cut bounds of Lemma 11 turn into the flow bound of Theorem 7.
Formalization Note The paper does not prove this; it invokes LP duality (§2.2, p. 796). The hypotheses and connectivity make the max-flow finite and positive. The normalization is the standing assumption of §2.3.
import Mathlib import Definitions.Def_LeightonRao_Product_Setting
namespace LeightonRao.Product
theorem lp_duality {V : Type} [Fintype V] [DecidableEq V] (N : Network V) (hconn : IsConnectedNet N)
(π : V → ℝ) (hπ : IsPMFPWeight π) (hp : 2 ≤ (support π).card) :
(∀ d : V → V → ℝ, IsDistanceFunction d → SatisfiesPMFPConstraint N π d →
maxFlow N (productDemand π) ≤ totalWeight N d) ∧
(∃ d : V → V → ℝ, IsDistanceFunction d ∧ SatisfiesPMFPConstraint N π d ∧
totalWeight N d = maxFlow N (productDemand π)) := by sorry
end LeightonRao.Product
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.