Pathology of Traveling-Salesman Subtour-Elimination Algorithms

Mandell Bellmore and John C. Malone
Additional contact information
Mandell Bellmore: The Johns Hopkins University, Baltimore, Maryland
John C. Malone: McKinsey and Company, New York, New York

Operations Research, 1971, vol. 19, issue 2, 278-307

Abstract: The traveling-salesman problem has been the target of a substantial number of computational algorithms over the last two decades. Reported computational experience with these algorithms varies widely; authors, however, have generally failed to explain this variation adequately, or to offer predictive theories for their approaches. This paper (a) develops an underlying theory for the problem, (b) predicts pathological performance of some existing techniques, and (c) presents two algorithms, based upon the theory, with predictable polynomial growth in expected computation time and resistence to pathological problems.

Date: 1971
References: Add references at CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.19.2.278 (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:19:y:1971:i:2:p:278-307

Access Statistics for this article

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