EAGER: New Techniques for Graph-TSP

旅行商问题(TSP)是一个组合优化的基准问题，它要求对给定网络中的所有城市进行最短的旅行。距离来自底层无向图的图形版本捕捉到了为解决这个问题而设计好的算法的相当大一部分难度。这一建议将加深对图-TSP问题改进近似算法设计的最新进展中使用的新技术的统一理解，并提出新的技术以实现最优性能保证。它还将仔细检查这些方法中的哪些将适用于问题的更一般度量版本，以及它们与问题的众所周知的子巡回消去线性规划松弛的关系。设计更好的启发式方法来解决典型的困难优化问题，可以提高我们解决各种实际应用中出现的更大实际规模实例的能力。这个项目将开发改进基本旅行商问题的启发式解的数学可证明性的方法。该方案开发的新方法将应用于容错最小距离网络设计中更广泛的问题类别，并在图论和组合优化方面带来新的见解。

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.