Canonical dual approach to solving the maximum cut problem |
| |
Authors: | Zhenbo Wang Shu-Cherng Fang David Y Gao Wenxun Xing |
| |
Institution: | 1. Department of Mathematical Sciences, Tsinghua University, Beijing, China 2. Department of Industrial and Systems Engineering, North Carolina State University, Raleigh, NC, USA 3. School of Science, Information Technology and Engineering, University of Ballarat, Ballarat, VIC, Australia
|
| |
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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|