江苏省运筹学会第二届理事会第三次会议暨2024学术年会于11月24日在无锡市成功召开。本次会议首次设立了江苏省运筹学会科学技术奖之青年科技奖。经过申报、通讯评审、现场答辩和专家评审等环节,最终五位青年学者荣获青年科技奖。南京大学数学学院赵秋兰凭借研究成果《图上的装填与覆盖问题》,获此荣誉。
《图上的装填与覆盖问题》成果简介
多面体组合学是组合最优化领域前沿的研究方向,是利用多面体、整数规划和线性规划等理论工具并结合组合结构的分析来研究组合优化问题。从20世纪60年代Edmonds对匹配多面体的研究至今,多面体理论和技术不仅被用来证明许多组合优化问题的多项式时间可解性 (如匹配问题、最大独立集问题),还被用于一些 NP-困难的组合优化问题的算法设计 (如旅行售货员问题、设施选址问题)。图上的装填与覆盖问题是多面体组合学中的经典问题, 一方面它们均可以表达为整数规划形式,另一方面许多组合优化问题都可以用超图的语言描述为装填与覆盖类型的问题。因此装填与覆盖问题历来都是多面体组合研究的重点和难点。在box-完美图的研究上,推广了著名组合学家 Lovász (2021年阿贝尔奖获得者, 1999年沃尔夫奖获得者, 匈牙利科学院主席) 关于完美图的多面体刻画,系统地研究了相关的线性系统具有盒式全对偶整数性(box-TDI)的完美图类,其中一个结果解决了组合优化之父Edmonds于1982年提出的关于parity图是box-完美图的猜想。首次给出了cycle Mengerian 非平面图类的刻画,被审稿人誉为“解决了本领域一个长期悬而未决的重要问题”。解决了图密度问题的强多项式时间可解性,此问题是Jensen和Toft (2015) 及Stiebitz 等人(2012)的著作中列出的公开问题。这些研究成果发表在SIAM Journal on Optimization、Mathematics of Operations Research、Journal of Combinatorial Theory, Series B 等国际重要学术期刊上。
获奖者简介
赵秋兰,现任南京大学数学学院副教授、硕士生导师,博士毕业于香港大学数学系。目前担任中国运筹学会图论组合分会理事,主持国家自然科学基金青年项目和面上项目,2019年入选江苏省“双创博士”。主要研究兴趣包括多面体组合、图论和排序论。目前在Mathematics of Operations Research, SIAM Journal on Optimization, Journal of Combinatorial Theory, Series B等期刊发表学术论文多篇。