Volume 24, Issue 6
An Effective Continuous Algorithm for Approximate Solutions of Large Scale Max-Cut Problems

Cheng-xian Xu, Xiao-liang He & Feng-min Xu

DOI:

J. Comp. Math., 24 (2006), pp. 749-760

Published online: 2006-12

Preview Full PDF 152 1743
Export citation
  • 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.

  • Keywords

Max-cut problems Algorithm Feasible direction method Laplacian matrix Eigenvectors

  • AMS Subject Headings

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address
  • BibTex
  • RIS
  • TXT
@Article{JCM-24-749, author = {}, title = {An Effective Continuous Algorithm for Approximate Solutions of Large Scale Max-Cut Problems}, journal = {Journal of Computational Mathematics}, year = {2006}, volume = {24}, number = {6}, pages = {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. }, issn = {1991-7139}, doi = {https://doi.org/}, url = {http://global-sci.org/intro/article_detail/jcm/8788.html} }
TY - JOUR T1 - An Effective Continuous Algorithm for Approximate Solutions of Large Scale Max-Cut Problems JO - Journal of Computational Mathematics VL - 6 SP - 749 EP - 760 PY - 2006 DA - 2006/12 SN - 24 DO - http://doi.org/ UR - https://global-sci.org/intro/article_detail/jcm/8788.html KW - Max-cut problems KW - Algorithm KW - Feasible direction method KW - Laplacian matrix KW - Eigenvectors AB - 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.
Cheng-xian Xu, Xiao-liang He & Feng-min Xu. (1970). An Effective Continuous Algorithm for Approximate Solutions of Large Scale Max-Cut Problems. Journal of Computational Mathematics. 24 (6). 749-760. doi:
Copy to clipboard
The citation has been copied to your clipboard