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 的时间指数才能找到最短旅行。 在这个问题没有得到解决的情况下，计算机科学的研究人员转而寻找有效的算法，这些算法总是能找到可证明的接近最佳的问题解决方案。 解决旅行推销员问题的最佳算法已为人所知近 40 年，它可以找到一条始终比最短可能旅行长不超过 50% 的旅行。该项目的目标是找到有效的算法，总能找到更接近最优路径的路径，而不是延长 50% 的时间。 最近提出了一些候选算法，它们可能比 40 年前的算法更好；它们在旅行商问题的特殊情况下给出了更好的界限，并且 PI 通过计算实验表明它们在实践中表现更好。 该项目的目标是尝试证明这些候选算法实际上确实表现更好（或证明它们没有）。 该项目将以重要的方式使用计算实验来帮助指导这些算法行为的数学证明。由于旅行商问题对于本科生甚至对计算机科学感兴趣的高中生来说都是众所周知的，PI希望让本科生参与部分研究，并让高中生接触到这项工作，以激发他们进一步学习计算机的兴趣科学。