一、报告题目
在固定拓扑结构上的堆垛机问题的求解算法
二、主讲人
许超教授
三、主讲人简介
许超，电子科技大学计算机科学与工程学院教授，博士生导师。许超主要从事组合优化和算法的基础研究，在Mathematical Programming、SICOMP、SODA等组合优化和算法的国际顶级期刊和会议上发表多篇学术论文。现主持国家自然科学基金优秀青年（海外）项目。
四、报告简介
考虑在图上的堆垛机问题（Stacker Crane Problem，SCP）。给定一组请求，其中每个请求都有一个取货地点和一个存货地点，目标是安排一个一次只能完成一个请求的堆垛机完成所有请求，同时行驶的距离最短。如果所有存货点和取货点相同，则问题为Steiner TSP（STSP）。但SCP的难度远远大于STSP：在树上，STSP有多项式时间算法，但在树上SCP却是NP-Hard问题。唯一已知的多项式时间可解的SCP实例是在路径或环上。有趣的是，在路径和环上，SCP和最小生成树问题的复杂度是等价的。
报告重新审视了路径和环上的SCP问题的算法，并演示了如何将该算法推广到固定的拓扑结构上，从而获得对于任意固定拓扑结构上的多项式时间算法，并猜想存在对于拓扑结构的SCP问题的参数算法。
五、邀请人
张鹏
六、时间
2024年5月27日（星期一）10:00-11:00
七、地点
软件学院办公楼310会议室
八、主办
新葡萄8883官网最新版
