Simulated annealing algorithm for the minimum weighted perfect euclidean matching problem
RAIRO - Operations Research - Recherche Opérationnelle, Volume 20 (1986) no. 3, pp. 177-197.
@article{RO_1986__20_3_177_0,
     author = {Lutton, Jean-Luc and Bonomi, Ernesto},
     title = {Simulated annealing algorithm for the minimum weighted perfect euclidean matching problem},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {177--197},
     publisher = {EDP-Sciences},
     volume = {20},
     number = {3},
     year = {1986},
     mrnumber = {872639},
     zbl = {0679.90051},
     language = {en},
     url = {http://archive.numdam.org/item/RO_1986__20_3_177_0/}
}
TY  - JOUR
AU  - Lutton, Jean-Luc
AU  - Bonomi, Ernesto
TI  - Simulated annealing algorithm for the minimum weighted perfect euclidean matching problem
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 1986
SP  - 177
EP  - 197
VL  - 20
IS  - 3
PB  - EDP-Sciences
UR  - http://archive.numdam.org/item/RO_1986__20_3_177_0/
LA  - en
ID  - RO_1986__20_3_177_0
ER  - 
%0 Journal Article
%A Lutton, Jean-Luc
%A Bonomi, Ernesto
%T Simulated annealing algorithm for the minimum weighted perfect euclidean matching problem
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 1986
%P 177-197
%V 20
%N 3
%I EDP-Sciences
%U http://archive.numdam.org/item/RO_1986__20_3_177_0/
%G en
%F RO_1986__20_3_177_0
Lutton, Jean-Luc; Bonomi, Ernesto. Simulated annealing algorithm for the minimum weighted perfect euclidean matching problem. RAIRO - Operations Research - Recherche Opérationnelle, Volume 20 (1986) no. 3, pp. 177-197. http://archive.numdam.org/item/RO_1986__20_3_177_0/

[1] D. Avis, A survey of heuristics for the weighted matching problem, Network, vol. 13, n° 4, 1983, 475-493. | MR | Zbl

[2] M. O. Ball, U. Derigs, An analysis of alternative strategies for implementing matching algorithms, Network, vol. 13, n° 4, 1983, 517-550. | MR | Zbl

[3] J. Beardwood, J. H. Halton, J. M. Hammersely, The shortest path through many points, Proc. of the Cambridge Phil. Society, vol. 55, 1959, 299-327. | MR | Zbl

[4] E. Bonomi, J. L. Lutton, The N-city travelling salesman problem: Statistical Mechanics and the Metropolis Algorithm, SIAM Review, vol. 26, n° 4, 1984. | MR | Zbl

[5] E. Bonomi, J. L. Lutton, The Asymptotic behaviour of quadratic sum assignment problems: a statistical mechanics approach, to be published in the Europ. J. Op. Res. | Zbl

[6] S. Geman, D. Geman, Stochastic relaxation, Gibbs distribution and the Bayesian restoration of images, IEEE Trans, Pattern Anal. Machine Intell., vol. PAMI-6, 1984, 721-741. | Zbl

[7] B. Gidas, Non-stationnary Markov Chains and Convergence of the annealing algorithm, J. Stat. Phys., vol. 39, n° 1/2, 1985. | MR | Zbl

[8] J. M. Hammersley, D. C. Handcomb, Monte-Carlo methods, Chapman and Hall, London, 1964. | Zbl

[9] M. Iri, K. Murota, S. Matsui, Heuristic for Planar Minimum-Weight Perfect Matching, Network, vol. 13, 1983, 67-92. | MR | Zbl

[10] S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi, Optimization by simulated annealing, Science, vol. 220, n° 4598, 1983, 671-680. | MR

[11] S. Kirkpatrick, Optimization by simulated annealing, quantitative studies, J. Stat. Phys., vol. 34, n° 516, 1984, 975-987. | MR

[12] E. L. Lawler, Combinatorial optimization: networks and matroids, Holt, Rinehart and Winston, New York, 1976. | MR | Zbl

[13] N. Metropolis, A. Rosenbluth, M. Rosenbluth, A. Teller, E. Teller, Equation of state calculations by fast computing machines. J. Chem. Phys., vol. 21, 1953, 1087-1092.

[14]C. H. Papadimitriou, The probabilistic analysis of matching heuristics, in Proc. 15th Ann. Allerton Conf. on Communication, Control and Computing, 1977, p. 368-378.

[15] C. H. Papadimitriou, K. Streightz, Combinatorial Optimization Aglorithms and Complexity, Prentice Hall, Englewood Cliffs, N-Y, 1982. | Zbl

[16] E. M. Reingold, R. E. Tayan, On a Greedy heuristic for complete matching, SIAM J. Comput., vol. 10, n° 4, 1981, 676-681. | MR | Zbl

[17] E. M. Reingold, K. J. Supowit, Divide and Conquer heuristics for minimum weighted Euclidean matching, SIAM J. Comput., vol. 12, n° 1 1983, 118-143. | MR | Zbl

[18] M. Weber, Th. M. Liebling, The Euclidean matching problem and the Metropolis algorithm, private communication. | Zbl

[19] Problem solving, The Economist, July 28, 1984, 70-71.