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