×

zbMATH — the first resource for mathematics

A new Lagrangian net algorithm for solving max-bisection problems. (English) Zbl 1220.05029
Summary: The max-bisection problem is an \(N\)P-hard combinatorial optimization problem. In this paper, a new Lagrangian net algorithm is proposed to solve max-bisection problems. First, we relax the bisection constraints to the objective function by introducing the penalty function method. Second, a bisection solution is calculated by a discrete Hopfield neural network (DHNN). The increasing penalty factor can help the DHNN to escape from the local minimum and to get a satisfying bisection. The convergence analysis of the proposed algorithm is also presented. Finally, numerical results of large-scale G-set problems show that the proposed method can find a better optimal solutions.

MSC:
05C10 Planar graphs; geometric and topological aspects of graph theory
05C85 Graph algorithms (graph-theoretic aspects)
90C27 Combinatorial optimization
Software:
SDPpack
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Murty, K.G.; Kabadi, S.N., Some \(\mathit{NP}\)-complete problems in quadratic and nonlinear programming, Mathematical programming, 39, 117-129, (1987) · Zbl 0637.90078
[2] Hastad, J., Some optimal in approachability results, (), 1-10
[3] Arora, S.; Karger, D.; Karpinski, M., Polynomial time approximation schemes for dense instance of \(\mathit{NP}\)-hard problems, (), 284-293 · Zbl 0968.68534
[4] K. Jansen, M. Karpinski, A. Lingas, A polynomial time approximation scheme for max-bisection on planer graphs, Electronic Colloquium on Computational Complexity, Report TR00-064, 2000.
[5] Goemans, M.X.; Williamson, D.P., Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM, 42, 1115-1145, (1995) · Zbl 0885.68088
[6] A. Frieze, M. Jerrum, Improved approximation algorithms for max \(k\)-cut and max bisection, in: Proc. 4th IPCO Conference, 1995, pp. 1-13. · Zbl 1135.90420
[7] Ye, Y., A.699-approximation algorithms for MAX-bisection, Mathematical programming, 90, 101-111, (2001) · Zbl 1059.90119
[8] Halperin, E.; Zwick, U., A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems, Random structures and algorithms, 20, 382-402, (2002) · Zbl 1017.68089
[9] Hopfield, J.J.; Tank, D.W., Neural computation of decisions in optimization problems, Biological cybernetics, 52, 141-152, (1985) · Zbl 0572.68041
[10] Cichochi, A.; Unbehauen, R., Neural networks for optimization and signal processing, (1993), John Wiley Sons New York
[11] Zhang, X.S., ()
[12] Simth, K.A., Neural networks for combinatorial optimization: a review of more than a decade of research, INFORMS journal on computing, 11, (1999)
[13] Dang, C.; He, L.; Kee Hui, I.P., A deterministic annealing algorithm for approximating a solution of the MAX bisection problem, Neural networks, 15, 441-458, (2002)
[14] Tamura, H.; Zhang, Z.; Xu, X.; Ishii, M.; Tang, Z., Larangian object relaxation neural network for combinatorial optimization problems, Neurocomputing, 68, 297-305, (2005)
[15] Lingyun, W.; Xiangsun, Z.; Juliang, Z., Application of discrete Hopfield-type neural network for MAX-cut problem, (), 1439-1444
[16] F. Rendle, H. Wolkowicz, A projection technique for partitioning the nodes of a graph, Technical Report 20, University of Waterloo, 1990.
[17] Cullum, J.; Donath, W.E.; Wolfe, P., The minimization of certain nondifferentiable sums of eigenvalues of symmetric matrices, Mathematical programming study, 3, 35-55, (1975) · Zbl 0355.90054
[18] Barnes, E.R.; Hoffman, A.J., Partitioning, spectra and linear programming, (1984), Academic Press USA · Zbl 0547.05059
[19] F. Alizadeh, J.P. Haeberly, M.V. Nayakkankuppam, M.L. Overton, S. Schmieta, SDPPack user’s guide—version 0.9beta, Technical Report TR1997-737, Courant Institute of Mathematical Science, NYU, New York, NY, June, 1997.
[20] Xu, F.; Xu, C.; Xue, H., A feasible direction algorithm without line search for solving MAX-bisection problem, Journal of computational mathematics, 23, 619-634, (2005) · Zbl 1086.65062
[21] C. Choi, Y. Ye, Solving sparse semidefinite programs using the dual scaling with an iterative solver, Working Paper, Department of Management Science, University of Iowa, Iowa, 2000.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.