Canonical dual approach to solving the maximum cut problem

Title: Canonical dual approach to solving the maximum cut problem
Creator: Wang, Zhenbo; Fang, Shucherng; Gao, David; Xing, Wenxun
Date: 2012
Type: Text; Journal article
Identifier: http://researchonline.federation.edu.au/vital/access/HandleResolver/1959.17/44443
Identifier: vital:4588
Identifier: https://doi.org/10.1007/s10898-012-9881-8
Identifier: ISSN:0925-5001
Abstract: This paper presents a canonical dual approach for finding either an optimal or approximate solution to the maximum cut problem (MAX CUT). We show that, by introducing a linear perturbation term to the objective function, the maximum cut problem is perturbed to have a dual problem which is a concave maximization problem over a convex feasible domain under certain conditions. Consequently, some global optimality conditions are derived for finding an optimal or approximate solution. A gradient decent algorithm is proposed for this purpose and computational examples are provided to illustrate the proposed approach. © 2012 Springer Science+Business Media, LLC.
Relation: Journal of Global Optimization Vol. , no. (2012), p. 1-11
Rights: Springer Science+Business Media, LLC.
Rights: This metadata is freely available under a CCO license
Subject: Canonical duality; Global optimization; Maximum cut; Perturbation method
Reviewed

		Thumbnail	File	Description	Size	Format