近日，理论计算机领域顶级会议SODA 2023放榜，我校计算机科学与工程学院（网络空间安全学院）算法与逻辑团队助理教授许超及其学生发表题为《A Polynomial Time Algorithm for Finding a Minimum 4-Partition of a Submodular Function》的论文。论文在许超的指导下，由2019级英才学院本科生刘宇豪、计算机科学与工程学院本科生史可共同参与完成。这是我校首次在SODA会议上发表学术论文。
该论文主要研究次模函数（submodular function）的最小k-partition问题。次模函数是一种抽象的组合函数，它是图和超图的割函数的延伸。次模函数最小k-partition是对图和超图的最小k-cut问题的自然延伸，也是组合优化领域最重要的问题之一。在此之前，图的k-cut问题对于任何指定的k都存在多项式时间求解的算法。而当图上的结论被推广到超图上时，次模函数的最小k-partition问题，只有在k≤3的情况下是已知可以在多项式时间内求解的。该论文给出了k=4时这一问题的第一个多项式时间算法。
图. 问题中的划分结构之间的一种关系
SODA，全称ACM-SIAM Symposium on Discrete Algorithms，是由计算机协会（ACM）和工业与应用数学学会（SIAM）两大国际学术组织联合主办，与STOC、FOCS一起被公认为算法领域的三大顶级学术会议，为CCF-A类，在整个计算机科学领域享有崇高声望，大陆平均每年只有个位数占比的文章可以被SODA会议录用。
电子科技大学算法与逻辑团队是由新西兰院士Bakh Khoussainov教授和肖鸣宇教授共同组建，周毅副教授、郝东副教授和许超助理教授等多位老师参与。该团队致力于基础理论研究，以探索算法难题和解决重要的科学问题为宗旨，激发和培养学生及青年老师对算法和基础理论的兴趣，为算法及相关研究方向感兴趣的师生提供一个交流平台。团队目前重点关注的研究方向包括：算法设计与分析（包括近似算法、参数算法、精确算法、在线算法等）、逻辑、图论与图算法、组合优化、算法工程、机制设计与算法博弈论、形式化方法与认证等。长期参与团队学习的本科生均能发表一篇高水平论文，并且多名学生在程序设计竞赛和数学建模竞赛中取得非常优异的成绩，在ACM程序设计竞赛中，团队多名学生打进了世界总决赛；在IEEE极限编程竞赛中团队学生连续两年获得世界第二名，四次进入世界前十名。
关闭窗口
APP下载
