From:raghavan@vuse.vanderbilt.edu (Vijay Raghavan)Newsgroups:sci.mathSubject:Re: Expected Max & Min for TSP pathsDate:5 Feb 92 23:36:53 GMTOrganization: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