报告题目：Approximation Algorithms for the k-depots Hamiltonian Path Problem

主 讲 人：刘朝晖  教授（华东理工大学）

报告时间：12月10日 09:00-10:00

报告地点：腾讯会议ID：894-586-603

主办单位：金沙集团wwW3354CC

报告摘要：We consider a multiple-depots extension of the classic Hamiltonian path problem where k salesmen are initially located at different depots. To the best of our knowledge, no algorithm for this problem with a constant approximation ratio has been previously proposed, except for some special cases. We present a polynomial algorithm with a tight approximation ratio of max{3/2,2-1/k} for arbitrary k≥1. Further, we develop a recursive framework to improve the approximation ratio to 3/2+ε. This framework is polynomial for fixed k and ε, and may be useful in improving the Christofides-like heuristics for other related multiple salesmen routing problems.

主讲人简介： 刘朝晖，华东理工大学数学学院教授、博士生导师，主要从事组合最优化和排序理论研究，获得2019年度上海市自然科学二等奖，2015年获宝钢优秀教师奖。目前担任中国运筹学会理事、中国运筹学会排序分会常务理事、上海市运筹学会副理事长。