nips nips2001 nips2001-186 nips2001-186-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Mikio L. Braun, Joachim M. Buhmann
Abstract: We consider noisy Euclidean traveling salesman problems in the plane, which are random combinatorial problems with underlying structure. Gibbs sampling is used to compute average trajectories, which estimate the underlying structure common to all instances. This procedure requires identifying the exact relationship between permutations and tours. In a learning setting, the average trajectory is used as a model to construct solutions to new instances sampled from the same source. Experimental results show that the average trajectory can in fact estimate the underlying structure and that overfitting effects occur if the trajectory adapts too closely to a single instance. 1
[1] J. M. Buhmann and M. Held. Model selection in clustering by uniform convergence bounds. Advances in Neural Information Processing Systems, 12:216- 222, 1999.
[2] R. Durbin and D. Willshaw. An analogue approach to the travelling salesman problem using an elastic net method. Nature, 326:689- 691, 1987.
[3] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchio Optimisation by simulated annealing. Science, 220:671- 680, 1983.
[4] S. Lin and B. Kernighan. An effective heuristic algorithm for the traveling salesman problem. Operations Research, 21:498- 516, 1973.
[5] P.D. Simic. Statistical mechanics as the underlying theory of
[6] G. Winkler. Image Analysis, Random fields and Dynamic Monte Carlo Methods, volume 27 of Application of Mathematics. Springer, Heidelberg, 1995. -sigma2 = O.03 i T.,...,:0.15OO:Xl Lenglt. : 5.179571 17.7 &: 17.6 j