A survey of heuristics for the weighted matching problem.

*(English)*Zbl 0532.90090This 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 |

##### Keywords:

exact algorithms; survey; heuristics; weighted matching problems; assignment problem; worst-case ratio bounds; absolute bounds; expected bounds##### 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.