Ellipsoid algorithm,separation oracle(选讲) 最小生成树的一种LP写法 ·max∑eEE CeXe ∑e∈ESxe≤lSI-1, ∑eeE(V)Xe=IVI-1 。0≤xe≤1 虽然是指数大小的LP,但是Ellipsoid algorithm只需要有 separation oracle,也能多项式时间解出来 24 Ellipsoid algorithm, separation oracle (选讲) 最小生成树的一种LP写法 • max ∑?∈@ �?�? • ∑?∈@(B) �? ≤ � − 1, ∀� ⊂ � • ∑?∈@(D) �? = � − 1 • 0 ≤ �? ≤ 1 虽然是指数大小的LP，但是Ellipsoid algorithm只需要有 separation oracle，也能多项式时间解出来 24