I’ve decided to read and summarize one great paper a week from this list. This week’s paper is the 1971 paper The Traveling-Salesman Problem and Minimum Spanning Trees: Part II by Held and Karp.
In a previous paper, Held and Karp considered a Lagrangian Relaxation approach to the traveling salesman problem (TSP), where 1-trees were used to provide a lower bound on an optimal tour. If one can quickly solve (or approximate) the considered Lagrangian Dual, strong lower bounds can be obtained. In this paper, they improve this procedure and effectively incorporate it into a branch-and-bound (B&B) algorithm. They triumphantly state that their method is “highly successful.”
In their words, the bounds are so sharp that the search trees are miniscule compared to those normally encountered in combinatorial problems of this type. In fact, they depict the B&B trees for eight different problems of 42 to 64 cities. Each B&B tree fits comfortably on one page. The following B&B tree is for the instance that was first considered by Dantzig, Fulkerson, and Johnson. No running time was given in their 1954 paper; their algorithm required human intervention to generate cuts. Held and Karp’s method solved it in under a minute.
Next up: J. Kruskal, On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem, Proceedings of the American Mathematical Society 7 (1956), 48.