A Tight Semidefinite Relaxation of the Cut Polytope
Miguel F. Anjos and Henry Wolkowicz
We present a tight semidefinite programming (SDP) relaxation for the
max-cut problem (MC) which improves on several previous SDP
relaxations in the literature. This new SDP relaxation is a
tightening of the SDP relaxation recently introduced by the authors,
and it inherits all the helpful properties of the latter. We show
that it is a strict improvement over the SDP relaxation obtained by
adding all the triangle inequalities to the well-known SDP relaxation.
Research Report CORR 2000-19 (8 March 2000),
Department of Combinatorics and Optimization,
University of Waterloo.