An efficient Lagrangian smoothing heuristic for Max-Cut |
| |
Authors: | Yong Xia Zi Xu |
| |
Institution: | 1.LMIB of the Ministry of Education; School of Mathematics and System Sciences,Beihang University,Beijing,Peoples’ Republic of China |
| |
Abstract: | Max-Cut is a famous NP-hard problem in combinatorial optimization. In this article, we propose a Lagrangian smoothing algorithm
for Max-Cut, where the continuation subproblems are solved by the truncated Frank-Wolfe algorithm. We establish practical
stopping criteria and prove that our algorithm finitely terminates at a KKT point, the distance between which and the neighbour
optimal solution is also estimated. Additionally, we obtain a new sufficient optimality condition for Max-Cut. Numerical results
indicate that our approach outperforms the existing smoothing algorithm in less time. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|