{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T09:05:47Z","timestamp":1777539947231,"version":"3.51.4"},"reference-count":27,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":8350,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1983,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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\u2010case ratio bounds, absolute bounds, and expected bounds. Applications to practical problems and some mathematical complements are also included.<\/jats:p>","DOI":"10.1002\/net.3230130404","type":"journal-article","created":{"date-parts":[[2007,5,11]],"date-time":"2007-05-11T17:18:55Z","timestamp":1178903935000},"page":"475-493","source":"Crossref","is-referenced-by-count":140,"title":["A survey of heuristics for the weighted matching problem"],"prefix":"10.1002","volume":"13","author":[{"given":"David","family":"Avis","sequence":"first","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","unstructured":"S.Akl A statistical analysis of various aspects of the travelling salesman problem. Ph.D. Thesis McGill University 1978."},{"key":"e_1_2_1_3_2","unstructured":"S.Akl A note on Euclidean matchings triangulations and spanning trees. Unpublished."},{"key":"e_1_2_1_4_2","first-page":"65","article-title":"Two greedy heuristics for the weighted matching problem","author":"Avis D.","year":"1978","journal-title":"Congr. Numer."},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/0898-1221(81)90084-5"},{"key":"e_1_2_1_6_2","unstructured":"D.AvisandL.Devroye An analysis of a decomposition heuristic for the assignment problem. Unpublished."},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100034095"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(80)90015-2"},{"key":"e_1_2_1_9_2","unstructured":"N.Christofides Worst case analysis of a new heuristic for the travelling salesman problem. Technical Report G.S.I.A. Carnegie\u2010Mellon University 1976."},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1147\/rd.134.0380"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1965-045-4"},{"key":"e_1_2_1_12_2","unstructured":"M.IriandA.Taguchi The determination of the pen movement of an XY\u2010plotter and its computational complexity (in Japanese).Proc. Spring Conf. of the O.R. Society of Japan P\u20108 1980 204\u2013205."},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(81)90103-4"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230130105"},{"key":"e_1_2_1_15_2","unstructured":"R. M.Karp A patching algorithm for the non\u2010symmetric travelling salesman problem. Technical Report UCB\/ERL\/M78\/2 Electronics Research Lab. University of California Berkeley 1978."},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/321138.321140"},{"key":"e_1_2_1_17_2","unstructured":"C. W.Lai A heuristic for the assignment problem and related bounds. Technical Report 81.20 McGill University 1981."},{"key":"e_1_2_1_18_2","unstructured":"C. H.Papadimitriou The probabilistic analysis of matching heuristics.Proc. 15th Allerton Conference on Communication Control and Computing 1977 pp.368\u2013378."},{"key":"e_1_2_1_19_2","volume-title":"Combinatorial Optimization: Algorithms and Complexity","author":"Papadimitriou C. H.","year":"1982"},{"key":"e_1_2_1_20_2","article-title":"Probabilistic analysis of divide and conquer heuristics for minimum weighted Euclidean matching","author":"Reingold E. M.","journal-title":"Networks."},{"key":"e_1_2_1_21_2","doi-asserted-by":"publisher","DOI":"10.1137\/0210050"},{"key":"e_1_2_1_22_2","volume-title":"Packing and Covering","author":"Rogers C. A.","year":"1964"},{"key":"e_1_2_1_23_2","doi-asserted-by":"crossref","unstructured":"J. M.Steele Subadditive Euclidean functional and non\u2010linear growth in geometric probability.Ann. Probability(1981)365\u2013376.","DOI":"10.1214\/aop\/1176994411"},{"key":"e_1_2_1_24_2","doi-asserted-by":"crossref","unstructured":"K. J.Supowit D. A.Plaisted andE. M.Reingold Heuristics for weighted perfect matching.Proc. 12th Annual ACM Symp. on Theory of Computing 1980 pp.398\u2013419.","DOI":"10.1145\/800141.804689"},{"key":"e_1_2_1_25_2","unstructured":"K. J.SupowitandE. M.Reingold Divide and conquer heuristics for minimum weighted Euclidean matching. Unpublished."},{"key":"e_1_2_1_26_2","article-title":"The travelling salesman problem and minimum matching in the unit square","author":"Supowit K. J.","journal-title":"SIAM J. Comput."},{"key":"e_1_2_1_27_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(80)90172-7"},{"key":"e_1_2_1_28_2","doi-asserted-by":"publisher","DOI":"10.1137\/0208036"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230130404","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230130404","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,20]],"date-time":"2023-10-20T02:59:16Z","timestamp":1697770756000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230130404"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1983,12]]},"references-count":27,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1983,12]]}},"alternative-id":["10.1002\/net.3230130404"],"URL":"https:\/\/doi.org\/10.1002\/net.3230130404","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1983,12]]}}}