报告时间：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日
