A Strengthened SDP Relaxation via a Second Lifting for the MAX-CUT Problem

Miguel Anjos and Henry Wolkowicz

We present a strengthened semidefinite programming, SDP, relaxation for the Max-Cut problem, MC, and for the general quadratic boolean maximization problem. The well-known SDP relaxation can be obtained via Lagrangian relaxation and results in an SDP with variable $X \in {\cal S}^n$, the space of $n \times n$ symmetric matrices, and $n$ constraints, $\diag(X)=e,$ where $e$ is the vector of ones. The strengthened bound is based on applying a {\em lifting procedure} to this well-known semidefinite relaxation after adding the nonlinear constraints $X^2-nX=0$ and $X\circ X=E.$ The lifting procedure is again done via Lagrangian relaxation and results in an SDP with variable $Y \in {\cal S}^{t(n-1)+1}$, where $t(r)=r(r+1)/2,$ and $2t(n-1)+1$ constraints. It is shown that the new bound obtained this way strictly improves the previous SDP bound, both empirically and theoretically.

Technical Report CORR-55 October, 1999 University of Waterloo Department of Combinatorics and Optimization Waterloo, Ontario N2L 3G1, Canada

Contact: hwolkowi@orion.math.uwaterloo.ca


 [PS]  [IP PAGE]  [SEARCH AGAIN]