EAGER: New Techniques for Graph-TSP

Carnegie Mellon University, Pittsburgh PA

Investigators

Abstract

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.