pcolsen@super.ORG (Peter C Olsen) (12/02/90)
Can anyone point me toward data for the Travelling Salesman problem with known solutions? I experimenting with some Neural Network approximations and I'd like some known standards against which to compare. 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. Thanks. Peter Olsen, pcolsen@super.super.org
mvp@tove.cs.umd.edu (Mahe Velauthapillai) (12/04/90)
[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