O'Reilly logo

In Pursuit of the Traveling Salesman by William J. Cook

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

9: Complexity

Is there or is there not a polynomial-time algorithm for obviously finite bounded integer programming? I mean, this is my sermon: Is there or is there not?

—Jack Edmonds, 1991.1

The pursuit of the salesman through ever larger numbers of cities has led to breakthroughs in mathematics, computing, and engineering, as well as advances in numerous practical applications. This is the pride and joy of TSP researchers. But the step-by-step approach has not answered the mother-of-all complexity questions: can we efficiently solve every instance of the TSP?

The fate of the salesman from this complexity point of view is tied to that of many other problems, including general integer programming, via the theory of Stephen Cook and Richard Karp. ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required