Loading...
research article
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.
Type
research article
Authors
Publication date
1986
Published in
Volume
30
Issue
3
Start page
85
End page
110
Note
PRO 86.02
Peer reviewed
REVIEWED
EPFL units
Available on Infoscience
February 13, 2006
Use this identifier to reference this record