摘要
最大割问题是图论中的一个典型的NP困难问题。文中基于最大割问题的半定规划松弛模型,给出了最大割问题的一种二次规划松弛模型,并且理论证明了提出的二次规划松弛模型要优于半定规划松弛模型。在该模型的基础上,利用分枝定界算法求解最大割问题。对小规模和中等规模的最大割问题分别作数值实验。实验表明分枝定界算法能够给出最大割问题一个好的近似解,是求解中小规模最大割问题的有效方法。
The max-cut problem is a standard NP-hard problem in graph graphic theory. Based on semidefinite programming relaxation model of the max-cut problem, a quadratic is presented. We have proven that quadratic programming relexation model programming relexation model is better than the semidefinite programming relaxation model in theory. Based on the model, we use the Branch-and-Bound algorithm to solve the max-cut problem. Numerical results for the small scale problems and the middle scale problems demonstrate that a better solution can be obtained by the algorithm, and the algorithm is an effective algorithm for the max-cut problem with a middle scale.
出处
《西安科技大学学报》
CAS
北大核心
2006年第4期541-544,共4页
Journal of Xi’an University of Science and Technology
关键词
最大割问题
二次规划
分枝定界
max-cut problem
quadratic programming
branch-and-Bound
