Lemma 16, p. 807 — a distance function satisfying the directed distance constraint yields a directed cut of ratio cost O(W log n)
ProvedLeightonRao.Directed.lemma_16approximationdirected-graphp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1sparsest-cut
Let be a strongly connected directed network on nodes and a distance function with total weight that satisfies the directed distance constraint . Then there is a nonempty proper with
to base .
Applied to an optimal dual solution (), it gives , the lower bound of Theorem 12.
Formalization Note The paper states "ratio cost ". The constant is Corollary 14's bound at ; it dominates Lemma 15's because for .
Preamble
import Mathlib import Definitions.Def_LeightonRao_Directed_Setting
Formal statement
namespace LeightonRao.Directed
/-- Leighton–Rao, Lemma 16, p. 807. A nonnegative distance function of total weight `W` satisfying
the directed distance constraint yields a directed cut of ratio cost at most `(1152/5) W log₂ n`
(Corollary 14's bound; it dominates Lemma 15's `12 W` since `log₂ n ≥ 1`). -/
theorem lemma_16 {V : Type} [Fintype V] [DecidableEq V] (N : DiNetwork V)
(hn : 2 ≤ Fintype.card V) (hconn : IsStronglyConnectedNet N)
(d : V → V → ℝ) (hd : ∀ u v, 0 ≤ d u v) (hW : SatisfiesDiConstraint N d) :
∃ U : Finset V, U.Nonempty ∧ Uᶜ.Nonempty ∧
diRatio N U ≤ (1152 / 5) * diTotalWeight N d * Real.logb 2 (Fintype.card V) := 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. 807, Lemma 16
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.