The Travelling Salesman Problem

Contributor(s): Professor William Cook | The general setting is the following. Complexity theory suggests there are limits to the power of general-purpose computational techniques, in engineering, science and elsewhere. But what are these limits and how widely do they constrain our quest for knowledge? The TSP can play a crucial role in this discussion, demonstrating whether or not focused efforts on a single, possibly unsolvable, model will produce results beyond our expectations. We discuss the history of the TSP and its applications, together with computational efforts towards exact and approximate solutions.