Book review of: In Pursuit of the Traveling Salesman; Mathematics at the Limits of Computation
Jan Karel Lenstra, David B. Shmoys · Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands · 2016
The traveling salesman problem, or TSP for short, poses both a complexity question and a computational challenge.The complexity question is a fundamental one: Can an optimal solution be found in polynomial time or, equivalently, is P equal to NP ?The answer to this question is worth eternal fame and, as a side benefit, one million dollars.The computational challenge is one of algorithm development and engineering: As long as we have to assume that P is not equal to NP, how well can we do in finding good or even provably optimal solutions to large instances of the TSP?The TSP as a mathematical problem was discussed by Karl Menger in Vienna and by Hassler Whitney in Princeton in the 1930s.The 1940s brought a practical interest in solving optimization problems that occurred in a logistical or industrial setting.George Dantzig proposed the linear optimization model for such problems and developed the simplex method for their solution.With this major advance came the realization of its limitations.Many decision problems of a combinatorial nature, for example, can be cast in linear terms with the additional constraint that the variables can take on only integral values.The TSP is a case in point.In fact, many of the concepts and techniques of combinatorial optimization were originally conceived for the TSP.