Simulated annealing algorithm for the minimum weighted perfect euclidean matching problem

 Access to full text

 Full (PDF)

1. [1] D. Avis, A survey of heuristics for the weighted matching problem, Network, vol. 13, n° 4, 1983, 475-493. Zbl0532.90090MR723694
2. [2] M. O. BALL, U. DERIGS, An analysis of alternative strategies for implementing matching algorithms, Network, vol. 13, n° 4, 1983, 517-550. Zbl0519.68055MR723696
3. [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. Zbl0118.35601MR109316
4. [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. Zbl0551.90095MR765672
5. [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. Zbl0598.90065
6. [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. Zbl0573.62030
7. [7] B. GIDAS, Non-stationnary Markov Chains and Convergence of the annealing algorithm, J. Stat. Phys., vol. 39, n° 1/2, 1985. Zbl0642.60049MR798248
8. [8] J. M. HAMMERSLEY, D. C. HANDCOMB, Monte-Carlo methods, Chapman and Hall, London, 1964. Zbl0121.35503
9. [9] M. IRI, K. MUROTA, S. MATSUI, Heuristic for Planar Minimum-Weight Perfect Matching, Network, vol. 13, 1983, 67-92. Zbl0503.68050MR693856
10. [10] S. KIRKPATRICK, C. D. GELATT, M. P. VECCHI, Optimization by simulated annealing, Science, vol. 220, n° 4598, 1983, 671-680. Zbl1225.90162MR702485
11. [11] S. KIRKPATRICK, Optimization by simulated annealing, quantitative studies, J. Stat. Phys., vol. 34, n° 516, 1984, 975-987. MR751723
12. [12] E. L. LAWLER, Combinatorial optimization: networks and matroids, Holt, Rinehart and Winston, New York, 1976. Zbl0413.90040MR439106
13. [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. [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. [15] C. H. PAPADIMITRIOU, K. STREIGHTZ, Combinatorial Optimization Aglorithms and Complexity, Prentice Hall, Englewood Cliffs, N-Y, 1982. Zbl0503.90060
16. [16] E. M. REINGOLD, R. E. TAYAN, On a Greedy heuristic for complete matching, SIAM J. Comput., vol. 10, n° 4, 1981, 676-681. Zbl0468.68072MR635425
17. [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. Zbl0501.68032MR687806
18. [18] M. WEBER, Th. M. LIEBLING, The Euclidean matching problem and the Metropolis algorithm, private communication. Zbl0595.90060
19. [19] Problem solving, The Economist, July 28, 1984, 70-71.