主 题: 计算与应用数学拔尖博士生系列论坛——Combinatorial Algorithms for MAX-CUT Problem Review on State-of-Art Algorithms and a Concurrent Evolutionary Framework
报告人: Chen Cheng (School of Mathematical Sciences, Peking University)
时 间: 2017-11-17 12:00-13:30
地 点: Room 1418, Sciences Building No. 1
12:00-12:30 lunch；12:30-13:30 Talk
Title: Combinatorial Algorithms for MAX-CUT Problem Review on State-of-Art Algorithms and a Concurrent Evolutionary Framework
Abstract: The MAX-CUT problem is one of the most famous graph partitioning problems, and its approximation algorithms play important roles in computational physics, image processing and other _elds. However, since the problem is an NP-hard one, the best cut cannot be obtained in polynomial time. Various optimization algorithms have been proposed, which can be generally divided into two types, combinatorial algorithms and continuous algorithms. In this report, we will review some state-of-art combinatorial (discrete) algorithms, analyze their strengths and weaknesses and generalize some useful frameworks.