Kuhn-Munkres Algorithm (a.k.a. The Hungarian Algorithm)

[anonymous]

On Friday, 19 February 2021 at 20:53:33 UTC, Sameer Pradhan wrote:

> I have a feeling that someone one on this forum might have more 
> information that could shed some more light on the best path to 
> take.

I'm solving the linear assignment problem (LAP), but not in D. 
Therefore I can't share code...

Some general notes:
* For larger problems
R. Jonker and A. Volgenant, "A Shortest Augmenting Path Algorithm 
for Dense and Sparse Linear Assignment Problems," Computing, vol. 
38, pp. 325-340, 1987.
   is often faster than the hungarian method. Scipy switched their 
implementation lately.
* you can use single commodity min-cost-flow algorithms for 
solving the LAP. In my experience lemon::NetworkSimplex [1] 
(written in C++ -> some glue code for a template free API needed) 
beats a reasonably good implementation of the hungarian method by 
a factor of 5-10.
    * min-cost flow can handle non-square matrices.
    * I have no implementation of the Jonker/Volgenant to compare 
to.



[1] http://lemon.cs.elte.hu/pub/doc/1.3.1/a00276.html