AF: EAGER: Approximation algorithms for the traveling salesman problem

Cornell University, Ithaca NY

Investigators

Abstract

The traveling salesman problem is a famous, well-studied problem within computer science and optimization. Given n cities, and a set of distances between each pair of cities, the goal is to find the shortest tour that visits each city once and returns to its starting point. There is an outstanding question of whether there is any efficient algorithm that given any set of n cities and the distances can find the shortest tour, or whether any such algorithm will always need time exponential in n to find the shortest tour. In the absence of the resolution of this question, researchers in computer science have instead looked for efficient algorithms that always find provably near-optimal solutions to the problem. The best such algorithm for the traveling salesman problem, known for almost 40 years now, is one that finds a tour that is always no more than 50% longer than the shortest possible tour. The goal of this project is to find efficient algorithms that always find tours significantly closer to the optimal than 50% longer. Recently some candidate algorithms have been proposed which might be provably better than the 40-year-old algorithm; they give provably better bounds in special cases of the traveling salesman problem, and the PI has shown through computational experiments that in practice they perform better. The goal of this project is to attempt to prove that these candidate algorithms do in fact perform better (or to show that they do not). The project will use computational experiments in significant ways to help direct the mathematical proofs of the behavior of these algorithms. Because the traveling salesman problem is well-known to undergraduates and even high school students interested in computer science, the PI hopes to involve undergraduates in parts of the research and expose high school students to the work in order to interest them in further study in computer science.