Canonical dual approach to solving the maximum cut problem

Canonical dual approach to solving the maximum cut problem

0.00 Avg rating0 Votes
Article ID: iaor20126019
Volume: 54
Issue: 2
Start Page Number: 341
End Page Number: 351
Publication Date: Oct 2012
Journal: Journal of Global Optimization
Authors: , , ,
Keywords: global optimization, max-cut problem, canonical duality theory (CDT)
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.

Reviews

Required fields are marked *. Your email address will not be published.