AF: Small: The Traveling Salesman Problem and Lightweight Approximation Algorithms

旅行商问题(TSP)很容易成为离散优化中最著名的问题。给定n个城市的集合以及从城市i到城市j的旅行成本c(i，j)，问题的目标是找到最便宜的旅行，即每个城市只访问一次并返回起点。在实际应用中，称为子回路LP的线性规划松弛法可以给出最优回路长度的极好的下界。然而，从理论的角度来看，对子巡回Lp界限的理解很少。30年来，人们已经知道它总是至少是最优旅行长度的2/3倍，也知道有这样的情况，它至多是最优旅行长度的3/4倍，但在收紧这些界限方面没有取得任何进展。有人猜想，子路线Lp总是至少是最优路线长度的3/4倍。本研究的目的就是解决这一猜想。由于这一目标非常雄心勃勃，因此提出了一些中间目标。理论计算机科学家已经深入研究了NP-Hard问题的近似算法；这些算法是多项式时间算法，总是提供可证明接近最优的解(在某些性能保证方面)。推动理论工作的主要问题是性能保证方面的改进，而不是算法是否可实现或实用。虽然理解可逼近性的极限是也应该是理论工作推进的问题之一，但人们也可以探索是否可以用计算强度低于目前文献中的算法来达到这些极限。我们称之为近似算法的轻量级版本的创建。这一探索在不失去该领域理论严谨性的情况下推进了逼近算法对实践的潜在影响，其智力价值在于有可能在解决与旅行商问题的子巡回LP相关的突出问题方面取得实质性进展，也在于使逼近算法中的一些优秀理论工作付诸实践。本研究的目的在于使优化问题的理论研究和实践研究更加紧密。在旅行商问题的情况下，我们有一个在实践中很好的界，但我们不理解它的理论性质。在近似算法的情况下，我们有一些非常好的理论算法，但它们往往不实用。我们想要了解旅行商问题的子圈Lp界的理论性质，并使逼近算法中的一些很好的理论工作付诸实践。

The traveling salesman problem (TSP) is easily the most famous problem in discrete optimization. Given a set of n cities and the costs c(i,j) of traveling from city i to city j for all i and j, the goal of the problem is to find the least expensive tour that visits each city exactly once and returns to its starting point. A linear programming relaxation of the problem called the subtour LP is known to give extremely good lower bounds on the length of an optimal tour in practice. Nevertheless, the subtour LP bound is poorly understood from a theoretical point of view. For 30 years it has been known that it is always at least 2/3 times the length of an optimal tour, and it is known that there are instances such that it is at most 3/4 times the length of an optimal tour, but no progress has been made in tightening these bounds. It has been conjectured that the subtour LP is always at least 3/4 times the length of the optimal tour. The goal of this research is to resolve this conjecture. Because this goal is very ambitious, a number of intermediate goals have been proposed. Theoretical computer scientists have intensively studied approximation algorithms for NP-hard problems; these are polynomial-time algorithms that always provide solutions that are provably close to optimal (in terms of some performance guarantee). The main issue driving theoretical work has been improvements in performance guarantee rather than whether the algorithms are implementable or practical. While understanding the limits of approximability is and should be one of the issues that theoretical work advances, one can also explore whether those limits can be reached with algorithms that are less computationally intensive than the ones currently in the literature. We call this the creation of lightweight versions of approximation algorithms. This exploration advances the potential impact of approximation algorithm on practice without losing the theoretical rigor of the field.The intellectual merit of the proposal lies in the possibility of making substantial progress in resolving outstanding problems related to the subtour LP for the traveling salesman problem, and also in making practical some of the outstanding theoretical work in approximation algorithms. The goal of this research lies in moving theoretical and practical studies of optimization problems closer to each other. In the case of the traveling salesman problem, we have a bound that is very good in practice, but we do not understand its theoretical properties. In the case of approximation algorithms, we have some very good theoretical algorithms, but they are often not practical. We would like to understand the theoretical properties of the subtour LP bound for the traveling salesman problem, and to make practical some of the good theoretical work in approximation algorithms.