- 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
- Hits: 1146
- Visitors: 1092
- Downloads: 0
Thumbnail | File | Description | Size | Format |
---|