§2.2, p. 796, directed analogue (§2.4) — LP duality: an optimal distance function has total weight W = f
ProvedLeightonRao.Directed.lp_dualitydirected-graphlinear-programminglp-dualitymulticommodity-flowp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a strongly connected directed network on nodes, and let be the max-flow of its directed uniform multicommodity flow problem. Then:
- every nonnegative distance function satisfying the directed distance constraint has total weight ; and
- some nonnegative distance function satisfying the distance constraint has
This is the linear programming duality between the concurrent flow LP and its dual (the distance LP). It reduces the lower bound of Theorem 12 to Lemma 16: a cut of small ratio cost is found from an optimal dual solution.
Formalization Note The paper states this duality in §2.2 for undirected UMFPs and uses its directed analogue in §2.4 ("The proof of Theorem 12 follows immediately from Lemma 16") without restating it. Strong connectivity and make the shortest-path distances well defined and the max-flow finite and positive.
Preamble
import Mathlib import Definitions.Def_LeightonRao_Directed_Setting
Formal statement
namespace LeightonRao.Directed
/-- Leighton–Rao, §2.2 p. 796, directed analogue used in §2.4: every nonnegative distance function
satisfying the directed distance constraint has total weight at least the max-flow, and some such
distance function has total weight exactly the max-flow. -/
theorem lp_duality {V : Type} [Fintype V] [DecidableEq V] (N : DiNetwork V)
(hn : 2 ≤ Fintype.card V) (hconn : IsStronglyConnectedNet N) :
(∀ d : V → V → ℝ, (∀ u v, 0 ≤ d u v) → SatisfiesDiConstraint N d →
diMaxFlow N diDemand ≤ diTotalWeight N d) ∧
(∃ d : V → V → ℝ, (∀ u v, 0 ≤ d u v) ∧ SatisfiesDiConstraint N d ∧
diTotalWeight N d = diMaxFlow N diDemand) := 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. 796, §2.2, LP duality sentence; directed analogue used in §2.4, p. 807
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.