Optimal solutions and ranks in the max-cut SDP

Daniel Hong, Hyunwoo Lee, Alex Wei

The max-cut problem is a classical graph theory problem which is NP-complete. The best polynomial time approximation scheme relies on \emph{semidefinite programming} (SDP). We stud…