Year: 2005
Journal of Computational Mathematics, Vol. 23 (2005), Iss. 6 : pp. 619–634
Abstract
This paper concerns the solution of the NP-hard max-bisection problems. NCP functions are employed to convert max-bisection problems into continuous nonlinear programming problems. Solving the resulting continuous nonlinear programming problem generates a solution that gives an upper bound on the optimal value of the max-bisection problem. From the solution, the greedy strategy is used to generate a satisfactory approximate solution of the max-bisection problem. A feasible direction method without line searches is proposed to solve the resulting continuous nonlinear programming, and the convergence of the algorithm to KKT point of the resulting problem is proved. Numerical experiments and comparisons on well-known test problems, and on randomly generated test problems show that the proposed method is robust, and very efficient.
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/2005-JCM-8842
Journal of Computational Mathematics, Vol. 23 (2005), Iss. 6 : pp. 619–634
Published online: 2005-01
AMS Subject Headings:
Copyright: COPYRIGHT: © Global Science Press
Pages: 16
Keywords: Max-Bisection problem Feasible direction algorithm NCP function Convergence.