最大割问题的二次规划方法

摘要

In this paper, a quadratic programming algorithm is presented to solve Max-cut problem. This algorithm can give a better bound of Max-cut problem by a convex quadratic programming resulted from the semidefinite programming relaxation. Then, the branch and bound method is used to gain the solution of Max-cut problem. Numerical results show that the algorithm is availability and efficient.%本文给出了最大割问题的二次规划算法.这种算法通过求解最大割问题的二次规划松弛给出了一种较好的界,然后用分支定界法得到了最大割问题的解.数值结果表明这种算法是非常有效的.