ISSN:
1432-5217
Keywords:
euclidean combinatorial optimization
;
matching problems
;
simulated annealing
;
geometric probability
;
asymptotic behaviour
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
,
Economics
Description / Table of Contents:
Zusammenfassung Euklidische Matching-Probleme bestehen darin, eine ausn Punkten bestehende Wolke derart inn/2 Paare zu partitionieren, daß die Summe der Abstände zwischen den Endpunkten der Paare minimal bzw. maximal wird. Vorliegende Arbeit beschreibt die Anwendung der „simulierten Abkühlung“, eines durch die Thermodynamik inspirierten Verfahrens, zur Lösung großer derartiger Probleme. Zudem wird das asymptotische Verhalten zufälliger euklidischer Matching-Probleme studiert, insbesondere werden numerische Angaben zur Konvergenzrate gegen die Asymptote gegeben.
Notes:
Abstract The Euclidean matching problem consists in partitionning a cloud ofn points inton/2 pairs such that the sum of the euclidean distances between the endpoints of each couple is minimized, 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 of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01919172
Permalink
