Euclidean Matching Problems and the Metropolis Algorithm
The Euclidean matching problem consist in partitionning a cloud of n points into n/2 pairs such that the sum of the euclidean distances between the endpoints of each couple is minmized, resp. maximized. In this paper the thermodynamically inspired approach of simulated annealing is applied to find good approximations to large scale problems of the above kind. Also the asymptotic behaviour of random euclidean matching problems is studied, in particular computational results on the rate of convergence towards the asymptote are given.