【理学院】The Steiner traveling salesman problem with online edge blockages

报告题目：The Steiner traveling salesman problem with online edge blockages

报告摘要：We consider the online Steiner Traveling Salesman Problem. In this problem, we are given an edge-weighted graph $G = (V, E)$ and a subset $D \subseteq V$ of destination vertices, with the optimization goal to find a minimum weight closed tour that traverses every destination vertex of $D$ at least once. During the traversal, the salesman could encounter as many as $k$ non-recoverable blocked edges. The edge blockages are real-time, meaning that the salesman knows about a blocked edge whenever it occurs. We first show a lower bound on the competitive ratio and present an online optimal algorithm for the problem. While this optimal algorithm has non-polynomial running time, we present another online polynomial- time asymptotically optimal algorithm for the problem.

报告人：Guohui Lin，Professor（University of Alberta, Canada）

时 间：6月12日（本周四）下午 15：20—16：20

地 点：18-918（理学院会议室）

人物名片：

Guohui Lin is a full professor of computing science at the University of Alberta, Canada. He received his BSc in applied mathematics from ZhejiangUniversity and PhD in theoretical computer science from Chinese Academic Sciences. He did the postdoc research at University of Vermont, McMasterUniversity and University of Waterloo. He joined the University of Alberta in 2001. His major research areas are algorithm design and analysis and omics. He has published more than 140 peer reviewed papers, served as associate editors for four international journals, and been (co-)principle investigators for six multi-million-dollar projects in the past five years.