The research report Simple Efficient Solutions for Semidefinite Programming
describes an algorithm that can be applied to solve the SDP relaxation of the max-cut problem. Numerical tests were done using MATLAB 6 with the files in this directory.
Also available: a ps file with the latest numerical test.

Please note that these are MATLAB files. They do not include mex files. Therefore the speed is misleading when compared to other packages that are written in compiled languages. In addition, these files are under constant improvement. The CPU times are significantly better than those reported in the above cited Research Report.

The algorithm is based on an inexact Gauss-Newton (GN) method using preconditioned conjugated gradients (PCG) to solve the least squares problem.

Important features: q-quadratic convergence and high accuracy.

We use the PCG-type algorithm LSQR written (in MATLAB) by Michael Saunders and available on his web page.

Available from Hans Mittelmann:
benchmarks for two max-cut problems from SDPLIB (mcp250-1, mcp500-1),
for several packages.
Further details about the problems are available from SDPLIB.

See also Gset, a group of graph problems from Yinyu Ye
(from Brian Borchers' web page).