AN EFFECTIVE CONTINUOUS ALGORITHM FOR APPROXIMATE SOLUTIONS OF LARGE SCALE MAX-CUT PROBLEMS

An effective continuous algorithm is proposed to find approximate solutions of NP-hardmax-cut problems.The algorithm relaxes the max-cut problem into a continuous nonlinearprogramming problem by replacing n discrete constraints in the original problem with onesingle continuous constraint.A feasible direction method is designed to solve the resultingnonlinear programming problem.The method employs only the gradient evaluations ofthe objective function,and no any matrix calculations and no line searches are required.This greatly reduces the calculation cost of the method,and is suitable for the solutionof large size max-cut problems.The convergence properties of the proposed method toKKT points of the nonlinear programming are analyzed.If the solution obtained by theproposed method is a global solution of the nonlinear programming problem,the solutionwill provide an upper bound on the max-cut value.Then an approximate solution to themax-cut problem is generated from the solution of the nonlinear programming and providesa lower bound on the max-cut value.Numerical experiments and comparisons on somemax-cut test problems(small and large size)show that the proposed algorithm is efficientto get the exact solutions for all small test problems and well satisfied solutions for mostof the large size test problems with less calculation costs.

AN EFFECTIVE CONTINUOUS ALGORITHM FOR APPROXIMATE SOLUTIONS OF LARGE SCALE MAX-CUT PROBLEMS

An effective continuous algorithm is proposed to find approximate solutions of NP-hard max-cut problems.The algorithm relaxes the max-cut problem into a continuous nonlinear programming problem by replacing n discrete constraints in the original problem with one single continuous constraint.A feasible direction method is designed to solve the resulting nonlinear programming problem.The method employs only the gradient evaluations of the objective function,and no any matrix calculations and no line searches are required. This greatly reduces the calculation cost of the method,and is suitable for the solution of large size max-cut problems.The convergence properties of the proposed method to KKT points of the nonlinear programming are analyzed.If the solution obtained by the proposed method is a global solution of the nonlinear programming problem,the solution will provide an upper bound on the max-cut value.Then an approximate solution to the max-cut problem is generated from the solution of the nonlinear programming and provides a lower bound on the max-cut value.Numerical experiments and comparisons on some max-cut test problems(small and large size)show that the proposed algorithm is efficient to get the exact solutions for all small test problems and well satisfied solutions for most of the large size test problems with less calculation costs.