Phase Transitions and Backbones of the Asymmetric Traveling Salesman Problem

Details Phase Transitions and Backbones of the Asymmetric Traveling Salesman Problem Phase Transitions and Backbones of the Asymmetric Traveling Salesman Problem

2011-06-30

arxiv.org/abs/1107.0055v1

Journal Of Artificial Intelligence Research, Volume 21, pages 471-497, 2004

Computer Science

Artificial Intelligence

Scientific paper

10.1613/jair.1389

In recent years, there has been much interest in phase transitions of combinatorial problems. Phase transitions have been successfully used to analyze combinatorial optimization problems, characterize their typical-case features and locate the hardest problem instances. In this paper, we study phase transitions of the asymmetric Traveling Salesman Problem (ATSP), an NP-hard combinatorial optimization problem that has many real-world applications. Using random instances of up to 1,500 cities in which intercity distances are uniformly distributed, we empirically show that many properties of the problem, including the optimal tour cost and backbone size, experience sharp transitions as the precision of intercity distances increases across a critical value. Our experimental results on the costs of the ATSP tours and assignment problem agree with the theoretical result that the asymptotic cost of assignment problem is pi ^2 /6 the number of cities goes to infinity. In addition, we show that the average computational cost of the well-known branch-and-bound subtour elimination algorithm for the problem also exhibits a thrashing behavior, transitioning from easy to difficult as the distance precision increases. These results answer positively an open question regarding the existence of phase transitions in the ATSP, and provide guidance on how difficult ATSP problem instances should be generated.

Affiliated with

Also associated with

No associations

Rating

Phase Transitions and Backbones of the Asymmetric Traveling Salesman Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Phase Transitions and Backbones of the Asymmetric Traveling Salesman Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Phase Transitions and Backbones of the Asymmetric Traveling Salesman Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-480045