| A Continuation Algorithm for Max-Cut Problem |
| |
| 作者姓名： | Feng Min XU Cheng Xian XU Xing Si LI |
| |
| 作者单位： | [1]School of Science, Xi＇an Jiaotong University, Xi＇an 710002, P. R. China [2]State Key Laboratory of Structural Analysis for Industrial Equipment, Dalian University of Technology, Dalian 110000, P. R. China |
| |
| 基金项目： | Key Project supported by National Natural Science Foundation of China, 10231060;Acknowledgments The authors express their gratitude to the referees for very helpful and detailed comments. We are also wish to thank Professor Zhang Jianzhong of City University of Hong Kong for his carefully reading and revising the paper. |
| |
| 摘 要： |
|
| 关 键 词： | 极大切割问题 NCP函数 凸函数 拉格朗日罚函数法 |
| 收稿时间： | 23 December 2004 |
| 修稿时间： | 2004-12-232005-04-28 |
A Continuation Algorithm for Max-Cut Problem |
| |
| Feng Min XU Cheng Xian XU Xing Si LI.A Continuation Algorithm for Max-Cut Problem[J].Acta Mathematica Sinica,2007,23(7):1257-1264. |
| |
| Authors: | Feng Min Xu Cheng Xian Xu Xing Si Li |
| |
| Institution: | (1) School of Science, Xi’an Jiaotong University, Xi’an 710002, P. R. China;(2) State Key Laboratory of Structural Analysis for Industrial Equipment, Dalian University of Technology, Dalian 110000, P. R. China |
| |
| Abstract: | A continuation algorithm for the solution of max-cut problems is proposed in this paper. Unlike the available semi-definite relaxation, a max-cut problem is converted into a continuous nonlinear programming by employing NCP functions, and the resulting nonlinear programming problem is then solved by using the augmented Lagrange penalty function method. The convergence property of the proposed algorithm is studied. Numerical experiments and comparisons with the Geomeans and Williamson randomized algorithm made on some max-cut test problems show that the algorithm generates satisfactory solutions for all the test problems with much less computation costs. |
| |
| Keywords: | max-cut problem NCP function convex function augmented Lagrange penalty function method |
| 本文献已被 维普 SpringerLink 等数据库收录！ |
