k-边不交受限最短路问题的最优绝对近似算法
科研大讨论系列报告
报告题目(Title)：k-边不交受限最短路问题的最优绝对近似算法
报告人(Speaker)：徐大川教授 （北京工业大学）
地点(Place)：后主楼1124
时间(Time)： 2024 年 4 月 26 日（周五） 14:30--15:30
邀请人(Inviter)：徐敏
报告摘要
处理NP难问题，除了基于比值的近似算法之外，另一个非常重要的方法是基于差值的绝对近似算法。这两种近似算法相互补充，提供了对问题的全面理解。当目标值是整数时，误差为1的绝对近似算法被称为最优绝对近似算法。目前只有极少数NP难问题具有这种最优绝对近似算法。给定带有非负成本和延迟权重的有向图，k-边不交的受限最短路问题旨在找到满足延迟约束的连接源点s和汇点t的k条边不相交有向路径，最小化其总成本。本报告介绍基于线性规划舍入的最优绝对近似算法。算法的主要思想是：挖掘线性规划松弛基最优解的性质---分数边构成环，根据不同的情景选择分数边子集进行舍入，从而获得满足约束的k-1或 k条边不交路径。（Joint work with Yue Sun, Donglei Du, and Longkun Guo）
主讲人简介
徐大川，北京工业大学数学系运筹学与控制论责任教授，数学/统计学博士生导师，北京工业大学区块链研究中心副主任(2018-至今)。2002年于中国科学院数学与系统科学研究院获得博士学位。研究兴趣包括：组合优化、近似算法、机器学习与优化、博弈论等。担任APJOR、JORSC等期刊编委。获中国运筹学会2022年度“最美科技工作者”。主持国家自然科学基金8项, 与国内某著名公司合作完成通讯网络优化、深度学习中的优化算法课题2项，结题被评为优秀。出版学术专著2部，在《Mathematical Programming》、《Operations Research》、《INFORMS Journal on Computing》、《Algorithmica》等发表学术论文100余篇。
