EN
2022年03月24日研究成果

组合问题的谱理论和谱算法

邵嗣烘团队

北京大学副教授、智源青年科学家邵嗣烘团队从四类基本的图割问题入手,提出了集对形式的Lovász扩展,给出了几类典型图上组合优化问题的连续等价形式。基于上述连续等价形式,团队提出了求解最大割问题和anti-Cheeger问题的连续迭代算法,在G-set测试集上可以给出和当前最佳值相当的数值结果。同样受益于集对形式Lovász扩展的一阶齐次以及分片线性,和等价连续优化问题的变分结构,研究人员发展了Lipschitz函数限制在凸多面体流形上的临界点理论,为发展组合问题的谱理论和谱算法迈出了关键的一步。

13.jpg

(图片来源:学者提供)


分享到: