Max-Cut partition Vinto two parts: S and T ● maximize the cut IC(S,T)I ●NP-hard 0.878~-approximation in poly-time by SDP easy 0.5-approximation C(S,T)={uw∈E|u∈S and v∈T}T S Max-Cut • partition V into two parts: S and T • maximize the cut |C(S,T)| • NP-hard • 0.878~-approximation in poly-time by SDP • easy 0.5-approximation C(S, T) = {uv ￾ E | u ￾ S
v ￾ T}