Max-Cut Instance:An undirected graph G(V,E). Solution:A bipartition of V into S and I that maximizes the cut E(S,T)={w,v}∈E|uw∈S∧v∈T}. max ∑aw integrality gap≥2 uw∈E S.t.yuw≤yuw+yww, u,v,w∈V 人 yuw+yuw+ywu≤2，，v,w∈V yuv∈{0,1}， u,v∈V V8>0:3G s.t.OPTLP(G)/OPTIP(G)>2-8Max-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 2 {0, 1}, yuv  yuw + ywv, yuv + yuw + ywv  2, 8u, v, w 2 V 8u, v, w 2 V 8u, v 2 V integrality gap ≥ 2 ∀ε>0: ∃G s.t. OPTLP(G)/OPTIP(G) > 2-ε