A projected gradient algorithm for solving the maxcut SDP relaxation
A projected gradient algorithm for solving the maxcut SDP relaxation
复制标题
DOI：
10.1080/10556780108805818
复制
发表时间：
2001-01
影响因子：
2.2
通讯作者：
S. Burer;R. Monteiro
中科院分区：
文献类型：
--
作者：
S. Burer;R. Monteiro
本文提出了一种求解最大割问题的半定规划松弛的投影梯度算法。再加上一个随机化的方法，这给出了一个非常有效的近似算法的最大割问题。我们报告的计算结果比较我们的方法与两个较早的成功的方法与尺寸高达7000的问题。
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.