From:           raghavan@vuse.vanderbilt.edu (Vijay Raghavan)
Newsgroups:     sci.math
Subject:        Re: Expected Max & Min for TSP paths
Date:           5 Feb 92 23:36:53 GMT
Organization:   Vanderbilt University School of Engineering, Nashville, TN, USA

In article <Feb.5.15.01.52.1992.2837@remus.rutgers.edu> clong@remus.rutgers.edu (Chris Long) writes:
<In article <1992Feb3.143829.24984@acsu.buffalo.edu>, Balamural K Ambati writes:
<> Beardwood, et al. (1959) published a report in which they showed that
<> the expected minimum distance of a Traveling Salesman Problem solution
<> is approximately 0.749 sqrt(N), where N points are randomly distributed
<> in the unit square.
<
<They arrived at this via Monte Carlo simulation, and I don't think
<that it's correct to even two decimal places.  I've seen two other
<numbers for this constant quoted and all three disagree.  Does anyone
<know the *actual* value for this constant to 3 or more decimal places?
<
<> I would like to know whether a similar expected MAXIMUM distance can be
<> computed?  Also, is the distribution of TSP solutions for an N city problem
<> known?
<
<Is this where the salesman is paid by the hour?  I don't know the
<answer, but my guess would be that it's approximately c*N^2, for some
<constant c.

   As long as we are guessing, I'll predict that the correct value of the 
constant .749... can be found in the Calcutta Mathematical Journal (c 1938) 
in a paper titled something like--"On the average height of jute crop in the 
month of September." I think Beardwood et al were aware of this paper (in fact 
it may even be a reference in their paper). It's been a long time since I read
it. Or maybe the reference can be found in Karp's paper on the Euclidean 
Traveling Salesman. I seem to remember that the C * sqrt (N) expected minimum
distance follows from results in the CMJ.

-- Vijay