## 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