邵嗣烘，教授（北京大学）

戴小英 研究员

Equivalent spectral theory for fundamental graph cut

12月5日（周四）16:00-17:00，蓝白楼311

We introduce and develop equivalent spectral theory for several fundamental graph cut problems including maxcut, the    Cheeger cut, anti-Cheeger cut, dual Cheeger problem and their useful variants. Using the resulting novel equivalent continuous formulations, we propose a simple inverse power (SIP) method for maxcut, the Cheeger cut and the anti-Cheeger cut, and its inner subproblem allows an explicit analytic solution, which constitutes the main reason why we call it ‘simple’. By fully exploiting the closed-form of the inner subproblem solution, we design a boundary-detected subgradient selection with which SIP is proved to be locally converged. Numerical experiments on G-set demonstrate that SIP outperforms Gurobi in terms of both computational cost and solution quality.