ISSN:
1432-5217
Keywords:
euclidean minimum matching problems
;
heuristic algorithms
;
simulated annealing
;
asymptotic behaviour
;
rate of convergence
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
,
Economics
Description / Table of Contents:
Zusammenfassung Wir stellen einen neuen heuristischen Algorithmus für minimale Matching-Probleme vor und wenden diesen auf das euklidische Problem mit zufÄlliger Punkteverteilung in 2 Dimensionen an. Auf “Simulated Annealing” basierend lÄuft der Algorithmus schneller als frühere heuristische Algorithmen und erreicht dabei suboptimale Lösungen gleich guter QualitÄt. Aus Konfigurationen mit bis zuN=20.000 Punkten im Einheitsquadrat schÄtzen wir, da\ für die LÄnge des minimalen Matchings asymptotischL∼Β√N mitΒ=0.3123±0.0016 gilt.
Notes:
Abstract We give a new heuristic algorithm for minimum matching problems and apply it to the Euclidean problem with random vertices in 2 dimensions. The algorithm is based on simulated annealing and performs in practice faster than previous heuristic algorithms yielding suboptimal solutions of the same good quality. From configurations with up toN=20.000 vertices in the unit square we estimate that the length of a minimum matching scales asymptotically asL∼Β√N with (Β=0.3123±0.0016.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01416735
Permalink
