AF: EAGER: Approximation algorithms for the traveling salesman problem

旅行推销员问题是计算机科学和优化领域中一个著名的、被广泛研究的问题。给定n个城市，以及每对城市之间的一组距离，目标是找到访问每个城市一次并返回起点的最短路线。有一个突出的问题是，是否存在一种有效的算法，在给定任意n个城市和距离的情况下，可以找到最短的行程，或者是否存在任何这样的算法总是需要n的指数时间来找到最短的行程。在这个问题没有解决方案的情况下，计算机科学的研究人员转而寻找有效的算法，总能找到可证明的接近最优的问题解决方案。对于旅行推销员问题，这类算法中最好的一种算法已经存在了近40年，它能找到一条总不超过最短可能路线50%的路线。这个项目的目标是找到有效的算法，总能找到比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.