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.