Great papers: The Traveling Salesman Problem and Minimum Spanning Trees: Part II

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.

Summary:

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.

Held and Karp B&B tree

Held and Karp B&B tree

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.

Advertisements

3 thoughts on “Great papers: The Traveling Salesman Problem and Minimum Spanning Trees: Part II

  1. Hussain Kharodawala

    Could you share an example of TSP solved using this algorithm, stating the steps in the algorithm ?

    Reply
      1. Hussain Kharodawala

        I have read the paper, and in one of my courses we are trying to get lower bounds using sub-gradient method. If you could share steps of algorithm in simplified text, that would suffice.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s