AF: EAGER: Approximation algorithms for the traveling salesman problem

AF：EAGER：旅行商问题的近似算法

• 批准号: 1552831
• 负责人: David Williamson
• 金额: $ 10万
• 依托单位: Cornell University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-09-01 至 2017-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1552831&HistoricalAwards=false
• 关键词: AF; EAGER; Approximation; algorithms; traveling

The traveling salesman problem is a famous, well-studied problem within computer science and optimization. Given n cities, and a set of distances between each pair of cities, the goal is to find the shortest tour that visits each city once and returns to its starting point. There is an outstanding question of whether there is any efficient algorithm that given any set of n cities and the distances can find the shortest tour, or whether any such algorithm will always need time exponential in n to find the shortest tour. In the absence of the resolution of this question, researchers in computer science have instead looked for efficient algorithms that always find provably near-optimal solutions to the problem. The best such algorithm for the traveling salesman problem, known for almost 40 years now, is one that finds a tour that is always no more than 50% longer than the shortest possible tour. The goal of this project is to find efficient algorithms that always find tours significantly closer to the optimal than 50% longer. Recently some candidate algorithms have been proposed which might be provably better than the 40-year-old algorithm; they give provably better bounds in special cases of the traveling salesman problem, and the PI has shown through computational experiments that in practice they perform better. The goal of this project is to attempt to prove that these candidate algorithms do in fact perform better (or to show that they do not). The project will use computational experiments in significant ways to help direct the mathematical proofs of the behavior of these algorithms. Because the traveling salesman problem is well-known to undergraduates and even high school students interested in computer science, the PI hopes to involve undergraduates in parts of the research and expose high school students to the work in order to interest them in further study in computer science.

旅行商问题是计算机科学和优化中一个著名的、研究得很好的问题。 给定n个城市，以及每对城市之间的一组距离，目标是找到访问每个城市一次并返回其起点的最短行程。 有一个突出的问题，是否有任何有效的算法，给定任何一组n个城市和距离可以找到最短的旅游，或者任何这样的算法是否总是需要时间指数在n找到最短的旅游。 在没有解决这个问题的情况下，计算机科学的研究人员转而寻找有效的算法，这些算法总是能找到问题的可证明的接近最优的解决方案。 对于旅行推销员问题，最好的算法是找到一个总是不超过50%的最短旅行时间的旅行，这个算法已经知道了将近40年。这个项目的目标是找到有效的算法，总是发现图尔斯显着接近最佳比50%长。 最近，一些候选算法已经被提出，这可能是可证明的比40岁的算法更好，他们给可证明的更好的界限在特殊情况下的旅行推销员问题，和PI已经通过计算实验表明，在实践中，他们表现得更好。 这个项目的目标是试图证明这些候选算法实际上执行得更好（或表明它们没有）。 该项目将以重要的方式使用计算实验来帮助指导这些算法行为的数学证明。由于旅行商问题是众所周知的本科生，甚至高中生感兴趣的计算机科学，PI希望参与大学生的部分研究和接触高中生的工作，以吸引他们在计算机科学的进一步研究。