十博体育官网,10bet国际官方网站

十博体育官网
学术讲座
  • 天元讲堂(6.13)Sihong Shao:Lovasz extension and graph cut
  • 浏览量:228 发布人: 十博体育官网:2019-06-12

  •   

    报告题目Lovasz extension and graph cut

    报告人:Sihong Shao (Peking University)

    时间2019613日(星期四)16:0017:00

    地点:10bet国际官方网站本部精正楼(数学楼)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.

      

      

    欢迎参加!

      


Copyright ©版权所有:十博体育官网管理后台
电话:0512-65112637 传真:0512-65112637  E-mail:sxxy@suda.edu.cn  地址:苏州市十梓街1号 邮编:215006 苏ICP备06032411号
XML 地图 | Sitemap 地图