LSAPE - Bipartite Matching

An easy-to-use C++/Matlab toolbox for finding optimal correspondences between the elements of two sets, i.e. solving bipartite matching problems (aka linear sum assignment problems), together with their dual (aka labeling problems). Equivalently, the toolbox allows to design dissimilarity measures between two sets, based on optimal correspondences.

The following problems are solved:

  • symmetric MIN-LSAP / minimal-cost perfect bipartite matching
  • asymmetric MIN-LSAP / minimal-cost maximum bipartite matching
  • MIN-LSAP with Error-correction (LSAPE) / minimal-cost error-correcting bipartite matching

with the Hungarian method (each problem is solved by a specific Hungarian algorithm).

Greedy algorithms are also proposed to find cheap assignments.

Sébastien Bougleux and Luc Brun (Normandie Univ, CNRS - ENSICAEN - UNICAEN, GREYC)

Évariste Daller (Normandie Univ, CNRS - ENSICAEN - UNICAEN, GREYC)
Benoit Gaüzère (Normandie Univ, INSA de Rouen, LITIS)

License CeCILL-C

Don't forget citations


version 4 (download)July 17 2017
version 3 (download)Feb. 3 2017
website onlineFeb. 3 2017