报告题目：Lovasz extension and graph cut
报告人：Sihong Shao (Peking University)
时间：2019年6月13日（星期四）16:00—17:00
地点：苏州大学本部精正楼（数学楼）307
摘要：A firm bridge between discrete data world and continuous math field should be tremendously helpful in data analysis. Along this direction, the Lovasz extension provides a both explicit and equivalent continuous optimization problem for a discrete optimization problem, for instance, the Cheeger cut problem. In this talk, we report a set-pair Lovasz extension which provides not only an answer to the dual Cheeger cut, anti-Cheeger cut, and max 3-cut problems, all of which cannot be handled by the Lovasz extension,but also works for the Cheeger cut and maxcut problems. In particular, the set-pair Lovasz extension enlarges the feasible region of resulting equivalent continuous optimization problems from a half space (resulted from the Lovasz extension ) to the entire space for the Cheeger cut and maxcut problems. On the other hand, it provides new possibilities for designing continuous optimization algorithms for combination problems on the practical side, too. As an illustration, we propose a simple continuous iterative algorithm for the maxcut problem which converges to a local optimum in finite steps. Here ‘simple’ means the inner subproblem is solved analytically and thus no optimization solver is called. Preliminary results on G-set demonstrate that the ratio between the best cut values achieved by the simple algorithm without any local breakout techniques and the best known ones is of at least $0.986$. In fact, equipped with some intuitive local breakout techniques, our simple maxcut algorithm may achieve the best cut values. Finally, we conduct a general discussion on graph k-cut problems.
欢迎参加！