報告時間：2023年3月27日 星期一 下午14：00—15：30

報告地點：電航樓219

報告摘要：

Given a set of cites along with the cost of travel between each pair of them, the traveling salesman problem, or TSP for short, is to find the cheapest way of visiting all the cites and returning to the starting point. It is well known that the TSP is NP-hard. However, if some order or a partial order of the cities to visit is given, polynomial-time solutions exist in most cases.

This talk gives a survey of recent work on the problems of touring a sequence of line segments, convex polygons in the plane and inside a polygonal region. The well-known watchman route problem, which asks for a shortest route along which a mobile robot can see a given polygon, can be also interpreted as a problem of touring a sequence of chords inside a polygon. Algorithmic techniques developed for the touring objects problems, including a data structure, called the last step shortest path maps, are investigated. An interesting result is that the traveling salesman problem for lines and rays in the plane can be solved in O() and O() time, respectively.

報告人簡介：

譚學厚現任日本東海大學情報理工學院計算機應用系教授，大連海事大學講座教授，并曾于1985年至1987年任教于南京大學計算機科學系。譚學厚1982年畢業于南京大學計算機科學系，1985年獲南京大學計算機科學系碩士學位，1991年獲日本名古屋大學工學部情報工學科博士學位。1992年至1993年在加拿大Montreal大學和McGill大學博士后工作站工作。譚學厚教授的主要研究方向是計算幾何，算法分析與設計，圖論和組合優化。主持日本學術振興會項目6項，在Theoretical Computer Science，Algorithmica, Computational Geometry: Theory and Applications，Discrete Applied Mathematics, Journal of Combinatorial Optimization等理論計算機領域內知名期刊發表學術論文50余篇。

信息科學技術學院

2023年3月23日