Year: 2006
Journal of Computational Mathematics, Vol. 24 (2006), Iss. 6 : pp. 749–760
Abstract
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.
You do not have full access to this article.
Already a Subscriber? Sign in as an individual or via your institution
Journal Article Details
Publisher Name: Global Science Press
Language: English
DOI: https://doi.org/2006-JCM-8788
Journal of Computational Mathematics, Vol. 24 (2006), Iss. 6 : pp. 749–760
Published online: 2006-01
AMS Subject Headings:
Copyright: COPYRIGHT: © Global Science Press
Pages: 12
Keywords: Max-cut problems Algorithm Feasible direction method Laplacian matrix Eigenvectors.