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.