An Efficient Algorithm for Solving the MAXCUT SDP Relaxation
Sam Burer and Renato D.C. Monteiro
In this paper we present a projected gradient algorithm for solving
the semidefinite programming (SDP) relaxation of the maximum cut
(MAXCUT) problem. Coupled with a randomized method, this gives a very
efficient approximation algorithm for the MAXCUT problem. We report
computational results comparing our method with two earlier successful
methods on problems with dimension up to $3000$.
Manuscript, School of ISyE, Georgia Tech, Atlanta, GA
30332, USA, December, 1998.
Contact: [email protected]