Perfect bipartite matching 定理：考虑二分图完美匹配的线性规划： max∑eEE CeXe subject to xe=1v∈V e∈δ(v) 0≤xe≤1He∈E 该LP的最优解一定是整数解 注意：这个LP在一般图上面并不一定是整数解的 7
Perfect bipartite matching 定理：考虑二分图完美匹配的线性规划： max ∑!∈# �!�! subject to 0 !∈$ % �! = 1 ∀� ∈ � 0 ≤ �! ≤ 1 ∀� ∈ � 该LP的最优解一定是整数解 注意：这个LP在一般图上面并不一定是整数解的 7
Ellipsoid algorithm,separation oracle(选讲) 最小生成树的一种LP写法 ·max∑eEE CeXe ·∑e∈Esxe≤lSI-1, ∑eeE(V)Xe=IV川-1 。0≤xe≤1 虽然是指数大小的LP,但是Ellipsoid algorithm只需要有 separation oracle,也能多项式时间解出来 8
Ellipsoid algorithm, separation oracle (选讲) 最小生成树的一种LP写法 • max ∑!∈# �!�! • ∑!∈#(%) �! ≤ � − 1, ∀� ⊂ � • ∑!∈#(') �! = � − 1 • 0 ≤ �! ≤ 1 虽然是指数大小的LP，但是Ellipsoid algorithm只需要有 separation oracle，也能多项式时间解出来 8