AF: Small: Looking Under Rocks: A Search for a Provably Stronger TSP Relaxation

旅行商问题是最广为人知的计算困难的问题之一。这个问题的目标是为一个推销员找到一条最便宜的路线，让他访问多个城市并返回家乡。目前还不知道是否有一种方法可以找到最好的可能的旅游，而不是列举指数级大量的可能的图尔斯。用于寻找最佳可能解决方案的广泛使用的算法涉及计算行程长度的下限，并且该下限越接近最佳可能行程的成本，这些算法运行得越快。本计画将探讨旅行商问题的其他下界，希望能找到更好的下界。更好地理解旅行商问题的下界有助于解决其他计算困难的问题。旅行商问题是一个很容易解释给大学生和高中生的问题。PI和他的研究生计划利用他们的研究作为一种手段，推广到这些学生，并在他们的项目涉及本科生。目前的方法计算的最佳解决方案的旅行推销员问题涉及反复解决一个众所周知的线性规划松弛的问题。虽然这个界限在实践中非常好（也就是说，它非常接近最优解的值），但尽管经过了几十年的研究，它的最坏情况行为仍然没有得到很好的理解。这个项目旨在研究旅行商问题的替代下界：它将从研究问题的半定规划松弛开始，并考虑可能添加到线性规划中的其他约束，以便能够证明比目前已知的更强的关于其最坏情况行为的陈述。 此外，该项目将考虑旅行推销员问题的一些尚未得到充分研究的变体，包括循环TSP;对于这个变体，我们甚至不确定该问题是否是NP难的或具有多项式时间算法。该奖项反映了NSF的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

The traveling salesman problem is one of the most widely known problems of computational difficulty. The goal of the problem is to find the cheapest route for a salesman to visit a number of cities and return to home. It is not known whether there is a means of finding the best possible tour short of enumerating the exponentially large number of possible tours. Widely used algorithms for finding the best possible solution involve computing lower bounds on the length of the tour, and the closer the bound is to cost of the best possible tour, the quicker these algorithms run. This project will investigate alternative lower bounds for the traveling salesman problem to the ones widely used in practice, in the hopes of finding a provably better lower bound. A better understanding of lower bounds for the traveling salesman problem should help with solving other computationally difficult problems. The traveling salesman problem is one that is easy to explain to undergraduates and high school students. The PI and his graduate student plan to use their research as a means of outreach to such students, and to involve undergraduates in their project.Current methods for computing the optimal solution to the traveling salesman problem involve repeatedly solving a well-known linear programming relaxation of the problem. Although this bound is extremely good in practice (that is, it is very close to value of an optimal solution), its worst-case behavior is not well understood, despite decades of research. This project intends to study alternative lower bounds for the traveling salesman problem: it will start by studying semidefinite programming relaxations of the problem, and also consider other constraints that might be added to the linear program in order to be able to prove stronger statements about its worst-case behavior than are currently known. In addition, the project will consider some variants of the traveling salesman problem that have not been as well-studied, including the circulant TSP; for this variant, we are not even sure if the problem is NP-hard or has a polynomial-time algorithm.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.