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 边界的理论属性，并将近似算法中的一些优秀理论工作付诸实践。