Quadratic Program for Max-Cut max Yuv uw∈E s.t. yuu≤lxu-xul, uw∈E xv∈{0,1}， u∈V quadratic program: max ∑a uv∈E s.t. yuw≤(1-Eucw),uw∈E xw∈{-1,1}， Vu∈V
Quadratic Program for Max-Cut 1 2 yuv (1 xuxv) yuv X uv2E T S max s.t. 8uv 2 E xv 2 {1, 1}, 8v 2 V quadratic program: , max X uv2E yuv s.t. yuv |xu xv|, xv 2 {0, 1}, 8uv 2 E 8v 2 V
Quadratic Program for Max-Cut max Yuv uw∈E S.t.yuw≤lxu-xv, /uv∈E xv∈{0,1， V∈V strictly quadratic program: max ∑1-xuo) uw∈E S.t. x=1, u∈V Nonlinear,non-convex!
Quadratic Program for Max-Cut T S strictly quadratic program: max s.t. 1 2 (1 xuxv) X uv2E x 8v 2 V 2 v = 1, Nonlinear, non-convex! max X uv2E yuv s.t. yuv |xu xv|, xv 2 {0, 1}, 8uv 2 E 8v 2 V