| 最大割问题的二次规划方法 |
| |
| 引用本文： | 王新辉,刘三阳,刘红卫. 最大割问题的二次规划方法[J]. 运筹学学报, 2003, 7(4): 31-37 |
| |
| 作者姓名： | 王新辉 刘三阳 刘红卫 |
| |
| 作者单位： | 西安电子科技大学应用数学系,西安,710071 |
| |
| 基金项目： | This research is supported by the Funds of Shaanxi Province National Science Grant No. 2001SL03 |
| |
| 摘 要： | 本文给出了最大割问题的二次规划算法。这种算法通过求解最大割问题的二次规划松弛给出了一种较好的界，然后用分支定界法得到了最大割问题的解。数值结果表明这种算法是非常有效的。
|
| 关 键 词： | 最大割问题 二次规划 分支定界法 无向图 |
A Quadratic Programming Algorithm for Max-cut Problem |
| |
| XINHUI WANG SANYANG LIU HONGWEI LIU. A Quadratic Programming Algorithm for Max-cut Problem[J]. OR Transactions, 2003, 7(4): 31-37 |
| |
| Authors: | XINHUI WANG SANYANG LIU HONGWEI LIU |
| |
| Affiliation: | XINHUI WANG SANYANG LIU HONGWEI LIU Department of Applied Mathematics,Xidian University,Xi'an 710071, |
| |
| Abstract: | 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. |
| |
| Keywords: | Max-cut problem Quadratic programming Branch and bound method. |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
