Speaker:

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

Time:

• 20:00-21:00 (Time in Beijing)
• September 28, 2022 (Wednesday)

Venue:

Online, Tencent Meeting: 939-212-933

Abstract:

在自动化仓储系统中，高效地完成存储和取出的操作有极大的意义。一个存储的操作是从任意一个入口拿到物品，放到对应的储存空间里一个特定的位置。一个取出的操作是从一个储存空间的特定的位置拿到物品，放到任意一个出口。将存储的操作和取出的操作对应起来，一次性完成，可以减少一些时间，而存储的顺序不同也可以改变耗时。如何在最短时间内完成所有的存储操作是一个重要的问题，这个问题等价于某一类型图上的高多重性非对称旅行商问题，而旅行商问题是经典的NP-hard的问题。然而，这类型图很特殊：存在一个常数大小的集合，使得任何长度为2的路径都包含这个顶点集中的一个顶点。这个报告将描述如何利用这些图的结构特性获得一个多项式时间算法。

Speaker Bio:

许超于2021年加入电子科技大学计算机科学与工程学院。现任算法与逻辑团队的助理教授。本科就读于美国纽约州立大学石溪分校数学系，于2018年在伊利诺伊大学香槟分校获得计算机博士学位。毕业后曾在多个科技和对冲基金公司担任研发科学家和软件工程师。研究方向为组合优化和算法的基础研究，相关工作发表于SODA, SICOMP, Mathematical Programming等算法和优化的知名会议和期刊。