AF: EAGER: Approximation algorithms for the traveling salesman problem

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

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.