The Traveling-Salesman Problem and Minimum Spanning Trees

Michael Held and Richard M. Karp
Additional contact information
Michael Held: IBM Systems Research Institute, New York, New York
Richard M. Karp: University of California, Berkeley, California

Operations Research, 1970, vol. 18, issue 6, 1138-1162

Abstract: This paper explores new approaches to the symmetric traveling-salesman problem in which 1-trees, which are a slight variant of spanning trees, play an essential role. A 1-tree is a tree together with an additional vertex connected to the tree by two edges. We observe that (i) a tour is precisely a 1-tree in which each vertex has degree 2, (ii) a minimum 1-tree is easy to compute, and (iii) the transformation on “intercity distances” c ij → C ij + π i + π j leaves the traveling-salesman problem invariant but changes the minimum 1-tree. Using these observations, we define an infinite family of lower bounds w (π) on C *, the cost of an optimum tour. We show that max π w (π) = C * precisely when a certain well-known linear program has an optimal solution in integers. We give a column-generation method and an ascent method for computing max π w (π), and construct a branch-and-bound method in which the lower bounds w (π) control the search for an optimum tour.

Date: 1970
References: Add references at CitEc
Citations: View citations in EconPapers (90)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.18.6.1138 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:18:y:1970:i:6:p:1138-1162

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().