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

AF：小：旅行商问题和轻量级近似算法

• 批准号: 1115256
• 负责人: David Williamson
• 金额: $ 35万
• 依托单位: Cornell University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-09-01 至 2016-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1115256&HistoricalAwards=false
• 关键词: AF; Small; Traveling; Salesman; Problem

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.

旅行商问题（TSP）是离散优化中最著名的问题。 给定一组n个城市，对于所有i和j，从城市i到城市j的旅行成本为c（i，j），问题的目标是找到最便宜的旅行，每个城市只访问一次，然后返回起点。一个线性规划松弛的问题，称为子旅游LP是已知的，在实践中给出了非常好的下限的最佳巡回赛的长度。 尽管如此，从理论的角度来看，人们对子巡演LP范围的了解还很有限。 30年来，人们已经知道，它总是至少2/3倍的长度的最佳巡回赛，它是已知的，有这样的情况下，它是最多3/4倍的长度的最佳巡回赛，但没有取得进展，在收紧这些界限。已经证明，子行程LP总是最优行程长度的至少3/4倍。本研究的目的就是解决这个问题。 由于这一目标非常雄心勃勃，因此提出了一些中期目标。理论计算机科学家已经深入研究了NP难问题的近似算法;这些是多项式时间算法，总是提供可证明接近最优的解决方案（在某些性能保证方面）。 推动理论工作的主要问题是性能保证的改进，而不是算法是否可实现或实用。 虽然理解近似性的极限是并且应该是理论工作进步的问题之一，但人们也可以探索这些极限是否可以通过计算强度低于目前文献中的算法来达到。 我们称之为近似算法的轻量级版本的创建。这种探索推进了近似算法对实践的潜在影响，而不失去该领域的理论严谨性，该建议的智力价值在于有可能在解决与旅行商问题的子行程LP相关的突出问题方面取得实质性进展，并使近似算法中的一些突出理论工作切实可行。本研究的目的在于使优化问题的理论和实践研究更加接近。 在旅行商问题的情况下，我们有一个在实践中非常好的界限，但我们不了解它的理论性质。 在近似算法的情况下，我们有一些非常好的理论算法，但它们往往不实用。 我们希望了解旅行商问题的子环LP界的理论性质，并将近似算法中的一些好的理论工作付诸实践。