×

Simulated annealing algorithm for the minimum weighted perfect Euclidean matching problem. (English) Zbl 0679.90051

Summary: A randomized heuristic derived from the Metropolis procedure is proposed to solve the minimum weighted matching problem. In the limit of large problems, the average behaviour of the minimum cost of the perfect matching in the two-dimensional Euclidean space is investigated for different probability distributions of points.

MSC:

90C27 Combinatorial optimization
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
65K05 Numerical mathematical programming methods
PDFBibTeX XMLCite
Full Text: DOI EuDML