Speaker:

Chao Xu (University of Electronic Science and Technology of China)

Time:

• 10:30-12:00 Beijing Time
• Oct 17, 2024 (Thursday)

Venue:

计算所环保园1号楼524会议室
腾讯会议号：605 5793 9921，密码：图灵机被提出的年份（4位）
B站直播网址：https://live.bilibili.com/22528138

Abstract:

In the Stacker Crane Problem (SCP), pairs of pickup and delivery points are designated on a graph, and a crane must visit these points to move objects from each pickup location to its respective delivery point. The goal is to minimize the total distance traveled. SCP is known to be NP-hard, even on tree structures. The only positive results, in terms of polynomial-time solvability, apply to graphs that are topologically equivalent to a path or a cycle. We propose an algorithm that is optimal for each fixed topology, running in near-linear time. This is achieved by demonstrating that the problem is fixed-parameter tractable (FPT) when parameterized by both the cycle rank and the number of branch vertices. This is joint work with Yike Chen and Ke Shi.

Speaker Bio:

许超，电子科技大学计算机科学与工程学院副教授，博士生导师，算法与逻辑团队成员。许超主要从事组合优化和算法的基础研究，在SODA、Mathematical Programming、SICOMP，等组合优化和算法的国际顶级期刊/会议上发表多篇学术论文。现主持国家自然科学基金优秀青年（海外）项目。