A projected gradient algorithm for solving the maxcut SDP relaxation
Samuel Burer, Renato D. C. Monteiro · Optimization methods & software · 2001
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 7,000.