3 Scopus citations


We empirically study phase transitions of the asymmetric Traveling Salesman. Using random instances of up to 1,500 cities, we show that many properties of the problem, including the backbone and optimal tour cost, experience sharp transitions as the precision of intercity distances increases across a critical value. We also show that the average computational cost of the well-known branch-and-bound subtour elimination algorithm for the problem also exhibits a threshold behavior, transitioning from easy to difficult as the distance precision increases. These results provide strong positive evidences to a decade-long open question regarding the existence of phase transitions of the Traveling Salesman.

Original languageEnglish
Pages (from-to)1202-1207
Number of pages6
JournalIJCAI International Joint Conference on Artificial Intelligence
StatePublished - 2003
Event18th International Joint Conference on Artificial Intelligence, IJCAI 2003 - Acapulco, Mexico
Duration: Aug 9 2003Aug 15 2003


Dive into the research topics of 'Phase transitions of the asymmetric traveling salesman'. Together they form a unique fingerprint.

Cite this