The Traveling-Salesman Problem

The traveling-salesman problem is that of finding a permutation P = (1 i₂i₃ … i_n) of the integers from 1 through n that minimizes the quantity

where the a_αβ are a given set of real numbers. More accurately, since there are only (n − 1)′ possibilities to consider, the problem is to find an efficient method for choosing a minimizing permutation. This problem was posed, in 1934, by Hassler Whitney in a seminar talk at Princeton University. There are as yet no acceptable computational methods, and surprisingly few mathematical results relative to the problem.