𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A survey of heuristics for the weighted matching problem

✍ Scribed by David Avis

Publisher
John Wiley and Sons
Year
1983
Tongue
English
Weight
909 KB
Volume
13
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

✦ Synopsis

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.

πŸ“œ SIMILAR VOLUMES

A comparison of optimization heuristics
A comparison of optimization heuristics for the data mapping problem
✍ Chrisochoides, Nikos; Mansour, Nashat; Fox, Geoffrey πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 421 KB πŸ‘ 2 views

In the paper we compare the performance of six heuristics with suboptimal solutions for the data distribution of two dimensional meshes that are used for the numerical solution of partial differential equations (PDEs) on multicomputers. The data mapping heuristics are evaluated with respect to seven