半岛官网在线登录

ENGLISH | 联系我们

半岛官网在线登录:【学术预告】在固定拓扑结构上的堆垛机问题的求解算法

【 发布日期:2024-05-21 】    作者:张鹏

一、报告题目

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

二、主讲人

许超教授                                            

三、主讲人简介

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

八、主办

半岛官网在线登录


半岛官网在线登录【集团】股份有限公司