Some Examples of Difficult Traveling Salesman Problems

C. H. Papadimitriou and K. Steiglitz
Additional contact information
C. H. Papadimitriou: Harvard University, Cambridge, Massachusetts
K. Steiglitz: Princeton University, Princeton, New Jersey

Operations Research, 1978, vol. 26, issue 3, 434-443

Abstract: We construct instances of the symmetric traveling salesman problem with n = 8 k cities that have the following property: There is exactly one optimal tour with cost n , and there are 2 k −1 ( k − 1)! tours that are next-best, have arbitrarily large cost, and cannot be improved by changing fewer than 3 k edges. Thus, there are many local optima with arbitrarily high cost. It appears that local search algorithms are ineffective when applied to these problems. Even more catastrophic examples are available in the non-symmetric case.

Date: 1978
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.26.3.434 (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:26:y:1978:i:3:p:434-443

Access Statistics for this article

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