计算与应用数学拔尖博士生系列论坛——Lovász extension, graph cut and its application on Max-Cut
主 题: 计算与应用数学拔尖博士生系列论坛——Lovász extension, graph cut and its application on Max-Cut
报告人: Weixi Zhang (Peking University)
时 间: 2018-04-27 12:00-13:30
地 点: Room 1560, Sciences Building No. 1
12:00-12:30 lunch；12:30-13:30 Talk
Abstract: A set-pair Lovász extension is established to construct equivalent continuous optimization problems for graph cut including the Max-cut, Cheeger cut, dual Cheeger cut, max 3-cut, anti-Cheeger cut problems, etc. Based on the explicit equivalent continuous optimization problem, we propose a simple continuous iterative algorithm for Max Cut, which converges to a local optimum in finite steps. The inner subproblem is solved analytically and thus no optimization solver is called. Preliminary results on G-set demonstrate the performance.