×

zbMATH — the first resource for mathematics

Euclidean matching problems and the Metropolis algorithm. (English) Zbl 0595.90060
The thermodynamically inspired approach of simulated annealing is used to solve large-scale Euclidean matching problems. The asymptotic behaviour of randomly generated problems is studied. A lot of computational results and illustrations are given.
Reviewer: J.Mitev

MSC:
90C10 Integer programming
65K05 Numerical mathematical programming methods
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Beardwood J, Halton JH, Hammersley JM (1959) The shortest path through many points. Proc. of the Cambridge Phil. Society, voll 55, pp 299–327 · Zbl 0118.35601 · doi:10.1017/S0305004100034095
[2] Bonomi E, Lutton JL (1984) The N-city travelling salesman problem: Statistical mechanics and the metropolis algorithm. SIAM Review 26/4 · Zbl 0551.90095
[3] Burkard RE, Derigs U (1980) Assignment and matching problems: Solution methods with FORTRAN-programs. Lecture Notes in Economics and Mathematical Systems 184, Springer · Zbl 0436.90069
[4] Cerny V (1982) A thermodynamical approach to the travelling salesman problem: an efficient simulation algorithm. Preprint, Inst. of Physics and Biophysics, Comenius Univ., Bratislava
[5] Dyer ME, Frieze AM, McDiarmid CJH (1984) Partitioning heuristics for two geometric maximization problems. Operations Research Letters 3/5 · Zbl 0551.90065
[6] Edmonds J (1965) Paths, trees and flowers. Canad J Math 17:449–467, and Matching and a polyhedron with 0–1 vertices. J Res NBS 69B:125–130 · Zbl 0132.20903 · doi:10.4153/CJM-1965-045-4
[7] Geman S, Geman D (1984) Stochastic relaxation, Gibbs distribution and Bayesian restoration of images. IEEE Trans Pattern Analysis and Machine Intelligence 6:721–741 · Zbl 0573.62030 · doi:10.1109/TPAMI.1984.4767596
[8] Hajek B (1985) Cooling schedules for optimal annealing. To appear in Mathematics of OR · Zbl 0652.65050
[9] Iri Masao, Marota Kazuo, Matsui Shouichi (1983) Neuristics for planar minimum-weight perfect matchings. Heuristics Networks 13:67–92 · Zbl 0503.68050
[10] Kirkpatrick S, Gelatt CD, Vecchi MP (1983) Optimization by simulated annealing. Science 22/4598:671–680 · Zbl 1225.90162 · doi:10.1126/science.220.4598.671
[11] Lutton JL, Bonomi E (1985) An efficient non-deterministic heuristic for the minimum weighted perfect matching problem: the Metropolis procedure
[12] Papadimitriou Christos H (1977) The probabilistic analysis of matching algorithms. Proceedings of the Annual Allerton Conference on Communication, Control and Computing, vol 15, pp 368–378
[13] Rossier Y, Troyon M, Liebling ThM (1985) Simulated annealing and the Euclidean traveling salemsan problem. Tech. Report RO 850 701, DMA EPF Lausanne
[14] Steele JM (1981) Subadditive Euclidean functionals and nonlinear growth in geometric probability. The Annals of Probability 9/3:365–376 · Zbl 0461.60029 · doi:10.1214/aop/1176994411
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.