Abstract
The traveling salesman problem is one of the most famous combinatorial problems, We identify a natural parameter for the two-dimensional Euclidean traveling salesman problem. We show that for random problems there is a rapid transition between soluble and insoluble instances of the decision problem at a critical value of this parameter. Hard instances of the traveling salesman problem are associated with this transition. Similar results are seen both with randomly generated problems and benchmark problems using geographical data. Surprisingly, finite-size scaling methods developed in statistical mechanics describe the behaviour around the critical value in random problems, Such phase transition phenomena appear to be ubiquitous. Indeed, we have yet to find an NP-complete problem which lacks a similar phase transition.
| Original language | English |
|---|---|
| Pages (from-to) | 349-358 |
| Number of pages | 10 |
| Journal | Artificial Intelligence |
| Volume | 88 |
| Issue number | 1-2 |
| Publication status | Published - Dec 1996 |
Keywords
- NP-complete problems
- complexity
- traveling salesman problem
- search phase transitions
- finite-size scaling
- easy and hard instances
- STATISTICAL-MECHANICS
- OPTIMIZATION