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.
This project initiated new work on developing effective heuristic methods for the TSP, a very important problem in optimization that is known to be computationally hard to solve exactly. Solving these optimization problems require tacking the combinatorial explosion in the number of candidate solutions so as to pick the best, and results in their computational intractability. The approximation algorithm approach taken in this proposal designs algorithms that run in much faster time than enumerating and scanning all solutions, yet always delivers a solution whose quality has a mathematically provable error ratio with respect to the best possible solution. The algorithm is designed so that this performance guarantee on the ratio of qualities is required to hold no matter what instance is provided as input to the method. The traveling salesperson problem (TSP) is a benchmark problem for combinatorial optimization that asks for a shortest length tour that visits all the cities in a given network. In the graph version that this proposal examined, the distances arise from an underlying undirected graph where every link has the same length. Despite its simplicity, this version captures a significant portion of the difficulty of designing good algorithms for solving this problem. This proposal developed a consolidated understanding of the new techniques used in recent developments in the design of improved approximation algorithms for the graph-TSP problem. It also suggested new methods to move towards performance guarantees approaching the limits of the underlying method. Designing better heuristic methods for solving such prototypically hard optimization problems improves our ability to solve larger real-scale instances arising in a variety of practical manifestations of the TSP.
