Max-Cut Instance:An undirected graph G(V,E). Solution:A bipartition of Vinto S and Ithat maximizes the cut E(S,T)={w,v}∈E|w∈S∧v∈T}. max Yuv uv∈E not linear S.t. yuu≤lEu-xul, Vuw∈E xu∈{0,1， Vu∈VMax-Cut Instance: An undirected graph . Solution: A bipartition of into and that maximizes the cut . G(V, E) V S T E(S, T) = {{u, v} ∈ E ∣ u ∈ S ∧ v ∈ T} T S max X uv2E yuv s.t. yuv  |xu ￾ xv|, xv 2 {0, 1}, 8uv 2 E 8v 2 V not linear