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 a_1i₂ + a_i₂i₃ + a_i₃i₄ + ⋯ + a_iₙ1, 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.