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.

Contact: [email protected]

[PS] [IP PAGE] [SEARCH AGAIN]