EAGER: New Techniques for Graph-TSP

旅行推销员问题（TSP）是一个组合优化的基准问题，它要求在给定的网络中访问所有城市的最短行程。图的版本，其中的距离产生于一个底层的无向图捕捉了设计好的算法来解决这个问题的困难的一个重要部分。该提案将制定一个巩固的理解，在最近的发展中使用的新技术，在设计改进的近似算法的图TSP问题，并建议新的走向最佳性能保证。它还将仔细研究这些将适用于更一般的度量版本的问题，以及他们的关系，著名的subtour消除线性规划松弛的问题。设计更好的启发式方法来解决原型硬优化问题可以提高我们的能力，解决更大的实际规模的情况下出现在各种实际应用。本计画将发展方法，以改善基本旅行推销员问题之启发式解的数学可证明品质。该提案开发的新方法将应用于设计容错最小距离网络的更广泛的问题，并在图论和组合优化方面带来新的见解。

The traveling salesperson problem (TSP) is a benchmark problem for combinatorial optimization that asks for a shortest tour that visits all the cities in a given network. The graph version where the distances arise from an underlying undirected graph captures a significant portion of the difficulty of designing good algorithms for solving this problem. This proposal will develop a consolidated understanding of the new techniques used in recent developments in the design of improved approximation algorithms for the graph-TSP problem and suggest new ones to move towards optimal performance guarantees. It will also examine carefully which of these will apply to the more general metric version of the problem, as well their relation to the well-known subtour elimination linear programming relaxation for the problem.Designing better heuristic methods for solving prototypically hard optimization problems can improve our ability to solve larger real-scale instances arising in a variety of practical applications. This project will develop methods for improving the mathematically provable quality of the heuristic solutions for the fundamental traveling salesperson problem. New methods developed by the proposal will find applications to broader classes of problems in designing fault-tolerant minimum-distance networks, and also lead to new insights in graph theory and combinatorial optimization.