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.
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. ...