Premium
A survey of heuristics for the weighted matching problem
Author(s) -
Avis David
Publication year - 1983
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230130404
Subject(s) - heuristics , matching (statistics) , euclidean geometry , mathematical optimization , mathematics , combinatorics , computer science , algorithm , statistics , geometry
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.