Canonical dual approach to solving the maximum cut problem
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. Copyright Springer Science+Business Media, LLC. 2012
Volume (Year): 54 (2012)
Issue (Month): 2 (October)
|Contact details of provider:|| Web page: http://www.springer.com/business/operations+research/journal/10898|
|Order Information:||Web: http://link.springer.de/orders.htm|
When requesting a correction, please mention this item's handle: RePEc:spr:jglopt:v:54:y:2012:i:2:p:341-351. See general information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Sonal Shukla)or (Christopher F Baum)
If references are entirely missing, you can add them using this form.