报告题目一：k-边不相交受限最短路问题的最优绝对近似算法

报 告 人： 徐大川 教授

报告时间：2024年4月13日9:00-11:30

报告地点：格物楼数学研究中心528报告厅

报告摘要：处理NP难问题，除了基于比值的近似算法之外，另一个非常重要的方法是基于差值的绝对近似算法。这两种近似算法相互补充，提供了对问题的全面理解。当目标值是整数时，误差为1的绝对近似算法被称为最优绝对近似算法。目前只有极少数NP难问题具有这种最优绝对近似算法。

给定带有非负成本和延迟权重的有向图，k-边不相交的受限最短路问题旨在找到满足延迟约束的连接源点s和汇点t的k条边不相交有向路径，最小化其总成本。本报告介绍基于线性规划舍入的最优绝对近似算法。算法的主要思想是：挖掘线性规划松弛基最优解的性质---分数边构成环，根据不同的情景选择分数边子集进行舍入，从而获得满足约束的k-1或 k条边不相交路径。（Joint work with Yue Sun, Donglei Du, and Longkun Guo）

报告人简介：徐大川，北京工业大学理学部运筹学与控制论责任教授，数学/统计学博士生导师，2002年于中国科学院数学与系统科学研究院获得博士学位。研究兴趣包括：机器学习与优化，近似算法等。任北京工业大学区块链研究中心副主任、中国运筹学会数学规划分会理事长等职务，荣获北京工业大学“我爱我师——我心目中最喜爱的老师”、北京工业大学优秀教师、中国运筹学会2022年度“最美科技工作者”等荣誉。主持国家自然科学基金8项，其中1项为重点项目，参加科技部国家重点研发计划1项，北京市自然科学基金重点项目2项；与国内某著名公司合作完成通讯网络优化、深度学习中的优化算法课题2项，结题时均被评为优秀。出版学术专著1部，在《Mathematical Programming》、《Operations Research》、《INFORMS Journal on Computing》、《Algorithmica》等发表学术论文100余篇。