图的最大二等分问题的投影梯度算法

A Projected Gradient Algorithm for Max Bisection

本文基于图的最大二等分问题已有的半定规划松弛模型,给出了原问题的等价模型及其新的半定 规划松弛模型,利用投影梯度算法求解该半定规划松弛模型,最后使用随机扰动算法求得原问题 的近似最优解。理论和数值试验表明该方法不仅可以在较高的精度下求解中小规模的图的最大二 等分问题,而且特别适合求解大规模的图的最大二等分问题。

Based on the semide?nite programming relaxation of Max Bisection available, the paper provides the equivalent model of Max Bisection and the new semide?nite programming relaxation. We use a projected gradient algorithm to solve the semide?nite programming relaxation. Coupled with a randomized method, this gives a very e?cient approximation algorithm for Max Bisection. The theory and numerical experiment show that the method can solve the small and moderate problem at a higher accurate, especially for the problems with a large scale.