A Continuation Algorithm for Max-Cut Problem

作     者：Feng Min XU Cheng Xian XU Xing Si LI Feng Min XU Cheng Xian XU School of Science,Xi’an Jiaotong University,Xi’an 710002,P.R.China Xing Si LI State Key Laboratory of Structural Analysis for Industrial Equipment,Dalian University of Technology,Dalian 110000,P.R.China

作者机构：School of ScienceXi'an Jiaotong University State Key Laboratory of Structural Analysis for Industrial EquipmentDalian University of Technology 

出 版 物：《Acta Mathematica Sinica,English Series》 (数学学报（英文版）)

年 卷 期：2007年第23卷第7期

页      面：1257-1264页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070105[理学-运筹学与控制论] 0701[理学-数学] 

基　　金：Key Project supported by National Natural Science Foundation of China 10231060 

主　　题：max-cut problem NCP function convex function augmented Lagrange penalty function method 

摘      要：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.