Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!uakari.primate.wisc.edu!ames!dftsrv!mimsy!tove.cs.umd.edu!mvp
From: mvp@tove.cs.umd.edu (Mahe Velauthapillai)
Newsgroups: comp.theory
Subject: Re: Wanted --- Traveling Salesman Problem data (with solution)
Message-ID: <28230@mimsy.umd.edu>
Date: 3 Dec 90 17:40:31 GMT
References: <9011300937.AA00204@geocub.greco-prog.fr> <38271@super.ORG> <38288@super.ORG>
Sender: news@mimsy.umd.edu
Reply-To: tim@normal.georgetown.edu (Timothy Law Snyder)
Organization: Georgetown U., Dept. of Computer Science, Washington, DC 20057
Lines: 43

[NOTE: This is posted for Tim Snyder by Mahe Velauthapillai.]

In article <38288@super.ORG> pcolsen@super.ORG (Peter C Olsen) writes:
>
>Can anyone point me toward data for the Travelling Salesman problem
>with known solutions?  I experimenting with some Neural Network
>...
>Even more valuable would be an estimate of the length of the optimal
>tour through n points generated by a spatial Poisson process with
>parameter lambda.
>...
>Peter Olsen, pcolsen@super.super.org

This problem has a long history and a series of papers that address
the question.  For a reasonable summary, see my paper with Mike Steele,
"Worst-case growth rates of some classical problems of combinatorial
optimization," SIAM J. Comput. 18, April, 1989, pp. 278-287.

Though this paper deals with the length of the TSP in the worst case,
we discuss the proabilistic results, for the growth rates are exactly
the same, namely, cn^{(d-1)/d}, where the constant c>0 depends
on the dimension d and n is the number of points.
The constants for the worst and probabilistic
cases are different.  The model for the probabilistic case
is random vectors in the unit d-cube.  Euclidean distance is the 
metric of choice, though the results easily scale to different regions 
and even different metrics.

The probabilistic proofs of convergence of TSP length over n^{(d-1)/d}
to a constant for the uniform case usually begin with proofs for
a Poisson process of intensity n, from which the uniform (or other) results
come via Tauberian theorems.

Recently, Avram and Bertsimas have determined an exact expression for
the minimum spanning tree constant, which is related to the TSP
constant.  This may really help you nail down the length of your 
TSPs.

Good luck!
 Timothy Law Snyder
 Department of Computer Science
 Georgetown University
 tim@guvax.georgetown.edu


Brought to you by Super Global Mega Corp .com