算法与逻辑团队本科生一作论文被计算机领域顶级会议IJCAI接收

近日,第32届国际人工智能联合会议IJCAI(International Joint Conference on Artificial Intelligence)放榜,我校计算机科学与工程学院(网络空间安全学院) 2019级本科生王正仁以第一作者身份撰写的关于松弛团搜索问题的论文《A Fast Maximum k-Plex Algorithm Parameterized by the Degeneracy Gap》被接收,届时该学生将在会议上展示成果并进行学术报告。该论文是在电子科技大学算法与逻辑团队周毅副教授(通讯作者)和肖鸣宇教授指导下完成,参与作者还有硕士生罗春雨同学。这也是王正仁同学继WWW 2022之后,本科阶段以第一作者发表的第二篇CCF-A类会议论文。

  k-Plex是一种松弛团模型,相比于传统团模型提高了对数据噪声的容忍度,在社区发现算法中常被用于社区的图论建模。最大k-Plex问题旨在搜索图中规模最大的k-Plex,该问题属于NP难问题。该论文基于参数算法理论,给出了一个快速的最大k-Plex的搜索算法,可以在大规模稀疏图中高效地搜索出最大k-Plex。

  论文揭示了大规模稀疏图中存在的小参数——退化差,并设计了相应的固定参数可解(Fixed-Parameter Tractable,FPT)算法。即在退化差参数有界的情况下,最大k-Plex问题能够在多项式时间内求解。此外,论文通过广泛地实验证明,退化差参数通常在输入图规模的对数数值范围内,并且所提出的固定参数可解算法达到了目前的最优性能。

  该论文中所提出的固定参数可解算法,其算法框架和运行实例分别如算法1和表1所示。

afde0ec796b475e07688aac7a5cdfb4f_263e9.p
2987a8637b89527fd845b9428d3ca2b2_263e9.p

  IJCAI是人工智能领域顶级会议,位列中国计算机学会推荐国际会议CCF-A类。本年度会议投稿超过4500篇,录用率仅为15%,会议将于8月在中国澳门召开。除以上介绍的这篇论文以外,算法与逻辑团队的研究生彭俊强以第一作者身份撰写的另一篇论文《Fast Algorithms for SAT with Bounded Occurrences of Variables》也被IJCAI 2023接收。

  王正仁,2022年度“成电杰出学生(本科生)”,现计算机学院大四本科生。他从大一开始以学院拔尖人才计划的形式进入算法与逻辑团队学习,主要专注于算法工程与理论方向上的前沿问题,以第一作者身份在CCF-A类会议WWW 2022和IJCAI 2023上发表两篇论文。

  电子科技大学算法与逻辑团队由新西兰院士Bakh Khoussainov教授和肖鸣宇教授共同组建,周毅副教授、郝东副教授和许超助理教授等多位老师参与。该团队致力于基础理论研究,以探索算法难题和解决重要的科学问题为宗旨,激发和培养学生及青年老师对算法和基础理论的兴趣,为算法及相关研究方向感兴趣的师生提供一个交流平台。团队目前重点关注的研究方向包括:算法设计与分析(包括近似算法、参数算法、精确算法、在线算法等)、逻辑、图论与图算法、组合优化、算法工程、机制设计与算法博弈论、形式化方法与认证等。

  每年有10余名对算法和数学感兴趣的本科生进入团队学习,科研能力明显提升,高水平论文等学术成果层出不穷。长期以来,学生在多项科技竞赛中斩获奖项,多名学生在程序设计竞赛和数学建模竞赛中取得非常优异的成绩。在ACM程序设计竞赛中,团队多名学生打进了世界总决赛;在IEEE极限编程竞赛中团队学生连续两年获得世界第二名,五次进入世界前十名;团队学生在2021年和2023年分别获得华为软件精英挑战赛全球总决赛冠军。