Statistical Physics of the Travelling Salesman Problem

Details Statistical Physics of the Travelling Salesman Problem Statistical Physics of the Travelling Salesman Problem

2000-01-07

arxiv.org/abs/cond-mat/0001069v1

Indian J. Theo. Phys. 47, 1 (1999)

Physics

Condensed Matter

Statistical Mechanics

10 pages, 5 figures, K. C. Kar Memorial Lecture, 1999 (to be published in Indian J. of Theo. Phys., Calcutta)

Scientific paper

If one places N cities on a continuum in an unit area, extensive numerical results and their analysis (scaling, etc.) suggest that the best normalized optimal travel distance becomes 0.72 for the Euclidean metric and 0.92 for the Manhattan metric. The analytic bounds, we discuss here, give 0.5 and 0.92 as the lower and upper bounds for the Euclidean metric, and 0.64 and 1.17 for the Manhattan metric. When the cities are randomly placed on a lattice with concentration p, we find that the normalized optimal travel distance vary monotonically with p. For p=1, the values in both Euclidean and Manhattan metric are 1, and as p tends to zero, the values are 0.72 and 0.92 in the Euclidean and Manhattan metrics respectively.The problem is trivial for p=1 but it reduces to the continuum TSP as p tends to zero. We do not get any irregular behaviour at any intermediate point, e.g., the percolation point. The crossover from the triviality to the NP- hard problem seems to occur at p<1.

Affiliated with

Also associated with

No associations

Rating

Statistical Physics of the Travelling 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 Statistical Physics of the Travelling Salesman Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Statistical Physics of the Travelling Salesman Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-720072