首页

科学计算系列报告(2024/4/13 9:00-11:30,报告人:徐大川)

发布人:日期:2024年04月12日 11:57浏览数:

报告题目一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余篇。



上一条:微分方程与动力系统系列报告(2024/4/18 报告人:胡烨耀)

下一条:科学计算系列报告(2024/4/12 9:00-12:20,报告人:程晋、翟剑、刘可伋、许伯熹、林怡雯)

【关闭】 打印    收藏