一、报告题目

在固定拓扑结构上的堆垛机问题的求解算法

二、主讲人

许超教授

三、主讲人简介

许超，电子科技大学计算机科学与工程学院教授，博士生导师。许超主要从事组合优化和算法的基础研究，在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会议室

八、主办

山东大学软件学院