A survey of heuristics for the weighted matching problem

Abstract

Abstract 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. Several heuristics 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.