报告题目： Steiner TSP with online edge blockages
时    间： 下周二，即4月28号上午10.00到11.00

报告人：  报告地点：二号楼309

报告摘要：The Steiner Traveling Salesman Problem with as many as k onlineedge blockages is considered. First a lower bound on the competitive ratiois shown; then an exponential-time online optimal algorithm for the problem ispresented; and lastly a polynomial-time online asymptotically optimalalgorithm is presented.  Experimental results show that thepolynomial-time online algorithm takes only a fraction of the running time of the offline optimalalgorithm, yet produces solutions of competitive quality to the offlineoptimal solutions.
报告人简历：Guohui Lin joined the University of Alberta as an
Assistant Professor of Computing Science in 2001, where he is now a fullprofessor with tenure. He obtained his PhD degree in Operations Researchfrom the Chinese Academy of Sciences

 in 1998, and his Bachelor of Sciencein Applied Mathematics from the Zhejiang University in 1993. Dr. Lin'sresearch is mainly in Algorithm Design and Analysis and Bioinformatics,
and has published more than 150 refereed articles in Computer Science,Bioinformatics, and other interdisciplinary sciences.