×

zbMATH — the first resource for mathematics

A survey of heuristics for the weighted matching problem. (English) Zbl 0532.90090
This survey paper reviews results on heuristics for two weighted matching problems: matchings where the vertices are points in the plane and weights are Euclidean distances, and the assignment problem. Exact algorithms for these problems have \(0(n^ 3)\) time bound, where n is the number of points. Several fast heuristics, typically with 0(n) and \(0(n^ 2)\) time bounds, are described in detail and results are given for worst-case ratio bounds, absolute bounds, and expected bounds. Applications to practical problems and some mathematical complements are also included.
Reviewer: T.Ibaraki

MSC:
90C35 Programming involving graphs or networks
65K05 Numerical mathematical programming methods
90-02 Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
05C35 Extremal problems in graph theory
68Q25 Analysis of algorithms and problem complexity
90C08 Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)
68R10 Graph theory (including graph drawing) in computer science
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] A statistical analysis of various aspects of the travelling salesman problem. Ph.D. Thesis, McGill University, 1978.
[2] A note on Euclidean matchings, triangulations and spanning trees. Unpublished. · Zbl 0631.05038
[3] Avis, Congr. Numer. pp 65– (1978)
[4] Avis, Comput. Math. Appl. 7 pp 251– (1981)
[5] and , An analysis of a decomposition heuristic for the assignment problem. Unpublished.
[6] Beardwood, Proc. Cambridge Philos. Soc. 55 pp 299– (1959)
[7] Bentley, J. Algorithms 1 pp 301– (1980)
[8] Worst case analysis of a new heuristic for the travelling salesman problem. Technical Report, G.S.I.A., Carnegie-Mellon University, 1976.
[9] Donath, IBM J. Res. Dev. pp 380– (1969)
[10] Edmonds, Canad. J. Math. 17 pp 449– (1965) · Zbl 0132.20903 · doi:10.4153/CJM-1965-045-4
[11] and , The determination of the pen movement of an XY-plotter and its computational complexity (in Japanese). Proc. Spring Conf. of the O.R. Society of Japan, P-8, 1980, 204–205.
[12] Iri, Information Processing Lett. 12 pp 206– (1981)
[13] Iri, Networks 13 pp 67– (1983)
[14] A patching algorithm for the non-symmetric travelling salesman problem. Technical Report UCB/ERL/M78/2, Electronics Research Lab., University of California, Berkeley, 1978.
[15] Kurtzberg, J. Assoc. Comput. Mach. 9 pp 419– (1962) · Zbl 0108.33303 · doi:10.1145/321138.321140
[16] A heuristic for the assignment problem and related bounds. Technical Report 81.20, McGill University, 1981.
[17] The probabilistic analysis of matching heuristics. Proc. 15th Allerton Conference on Communication Control and Computing, 1977, pp. 368–378.
[18] and , Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Englewood Cliffs, NJ, 1982. · Zbl 0503.90060
[19] Reingold, Networks.
[20] Reingold, SIAM J. Comput. 10 pp 676– (1981)
[21] Packing and Covering, Cambridge University, Cambridge, 1964. · Zbl 0176.51401
[22] Subadditive Euclidean functional and non-linear growth in geometric probability. Ann. Probability (1981) 365–376. · Zbl 0461.60029
[23] , and , Heuristics for weighted perfect matching. Proc. 12th Annual ACM Symp. on Theory of Computing, 1980, pp. 398–419.
[24] and , Divide and conquer heuristics for minimum weighted Euclidean matching. Unpublished. · Zbl 0501.68032
[25] Supowit, SIAM J. Comput.
[26] Walkup, Discrete Math. 31 pp 59– (1980)
[27] Walkup, SIAM J. Comput. 8 pp 440– (1979)
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.