Fundamental Theorem of Flow ·Flow network:D(V,E),s,t∈V,andc:E→R≥0 。Max-flow=min-cut ·With integral capacity c:E→Z≥o,the maximum flow is achieved by an integer flow f:E→Z≥o An elementary proof by augmenting path. An advanced proof by LP duality and integrality
• Flow network: , , and • Max-flow = min-cut • With integral capacity , the maximum flow is achieved by an integer flow . D(V, E) s, t ∈ V c : E → ℝ≥0 c : E → ℤ≥0 f : E → ℤ≥0 Fundamental Theorem of Flow • An elementary proof by augmenting path. • An advanced proof by LP duality and integrality
Estimate the Optima minimize 7x1+x2+ 53 VI subject to X1 T2 十33 ≥ 10 + + 5x1+ 2c2 T3 2 6 x1,x2,x3≥0 16 16≤( OPT s any feasible solution
Estimate the Optima minimize 7x1 + x2 + 5x3 subject to ≤ OPT ≤ any feasible solution x1 x2 + 3x3 ⇥ 10 5x1 + 2x2 x3 ⇥ 6 x1, x2, x3 0 + + ≤ = 16 16
Estimate the Optima minimize 7x1+x2+ 5c3 VI subject to y1 T2 十33 ≥ 10y1 + + V2 5x1+ 2c2 T3 ≥ 6y2 x1,2,x3≥0 10y1+6y2≤ OPT for any 41 5y2 7 -y1 + 2y2 ≤ 1 91,y2≥0 3y1 y2 ≤ 5
Estimate the Optima minimize 7x1 + x2 + 5x3 subject to ≤ OPT x1 x2 + 3x3 ⇥ 10 5x1 + 2x2 x3 ⇥ 6 x1, x2, x3 0 + + ≤ y1 y2 y1 y2 10y1 + 6y2 for any y1 + 5y2 ⇥ 7 y1 + 2y2 ⇥ 1 3y1 y2 ⇥ 5 y1, y2 0
Primal-Dual Primal: min 7x1 +x2+ 5c3 S.t. T1 X2 + 3c3 10 5c1 2c2 X3 ≥ 6 x1,x2,x3≥0 Dual: max 10y1+6y2 vdual feasible ≤primal OPT S.t. 41 + 5y2 ≤ 7 -y1 + 2y2 1 3y1 y2 5 LP∈NP∩coNP y1,y2 ≥0
Primal-Dual min 7x1 + x2 + 5x3 s.t. x1, x2, x3 0 10y1 + 6y2 y1 + 5y2 ⇥ 7 y1 + 2y2 ⇥ 1 3y1 y2 ⇥ 5 y1, y2 0 x1 x2 + 3x3 ⇥ 10 5x1 + 2x2 x3 ⇥ 6 max s.t. Primal: Dual: ∀dual feasible ≤ primal OPT LP ∈ NP∩coNP
Diet Problem calories Cl C2 Cn healthy vitamin 1 a11 a12 aIn ≥b1 。 。 vitamin m aml am2 amn ≥bm solution: X1 X2 Xn minimize the calories while keeping healthy
Diet Problem c1 c2 cn a11 a12 a1n am1 am2 amn vitamin 1 vitamin m ≥ b1 ≥ bm solution: x1 x2 xn calories healthy minimize the calories while keeping healthy