2025-03-14 Friday Sign in CN

Activities
Equivalent spectral theory for fundamental graph cut
Home - Activities
Reporter:
邵嗣烘,教授(北京大学)
Inviter:
戴小英 研究员
Subject:
Equivalent spectral theory for fundamental graph cut
Time and place:
12月5日(周四)16:00-17:00,蓝白楼311
Abstract:
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.