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倍，但在收紧这些界限方面没有取得进展。据推测，子线路长度至少为最优线路长度的3/4倍。这项研究的目的就是要解决这个猜想。由于这一目标非常宏大，因此提出了一些中间目标。理论计算机科学家已经深入研究了np困难问题的近似算法；这些是多项式时间算法，总是提供可证明接近最优的解决方案（就某些性能保证而言）。推动理论工作的主要问题是性能保证的改进，而不是算法是否可实现或实用。虽然理解近似性的极限是并且应该是理论工作推进的问题之一，但人们也可以探索是否可以使用比目前文献中计算强度更低的算法来达到这些极限。我们称之为近似算法的轻量级版本的创造。这一探索推进了逼近算法对实践的潜在影响，同时又不失该领域的理论严谨性。该建议的智力价值在于有可能在解决与旅行推销员问题的子线路LP相关的突出问题方面取得实质性进展，并使逼近算法中一些杰出的理论工作成为现实。本研究的目的在于使优化问题的理论和实践研究更加接近。在旅行推销员问题中，我们有一个在实践中非常好的边界，但是我们不了解它的理论性质。对于近似算法，我们有一些很好的理论算法，但它们通常不实用。我们想要了解旅行商问题的子游LP界的理论性质，并使一些好的理论工作在近似算法中得到应用。