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

8: Big Computing

I don’t think any of my theoretical results have provided as great a thrill as the sight of the numbers pouring out of the computer on the night Held and I first tested our bounding method.

—Richard Karp, 1985.1

The combination of ever-improving mathematical techniques, careful algorithm engineering, and powerful computing platforms has taken the TSP to dizzying heights, but the struggle with the salesman is far from over. Let’s see where we stand.

World Records

When it comes to TSP records, nothing comes close to topping the work of Dantzig, Fulkerson, and Johnson.

It is absolutely astonishing that the three authors were able to find an optimal solution of such a large TSP instance and to prove its optimality by manual computation. ...

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