The Traveling-Salesman Problem

The traveling-salesman problem is that of finding a permutation P = (1 i 2 i 3 ... i n ) of the integers from 1 through n that minimizes the quantity \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}$$a_{1i_2} + a_{i_2i_3} + a_{i_3i_4} + \cdots + a_{i_n1},$$\end{document} where the a (alpha)(beta) 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.