Phase Transitions of the Asymmetric Traveling Salesman
Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence. Pages 1202-1209.
Abstract
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.
@inproceedings{ijcai2003p171,
title = {Phase Transitions of the Asymmetric Traveling Salesman},
author = {Zhang, Weixiong},
booktitle = {Proceedings of the Eighteenth International Joint Conference on
Artificial Intelligence, {IJCAI-03}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Georg Gottlob},
pages = {1202--1209},
year = {2003},
url = {https://ijcai.org/proceedings/2003/171},
}
TY - CPAPER TI - Phase Transitions of the Asymmetric Traveling Salesman AU - Zhang, Weixiong T2 - Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, IJCAI-03 PB - International Joint Conferences on Artificial Intelligence PY - 2003 SP - 1202 EP - 1209 UR - https://ijcai.org/proceedings/2003/171 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
