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

[Sameer Pradhan]

On Saturday, 20 February 2021 at 07:50:40 UTC, anonymous wrote:
> * 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

Thanks for these details! It is interesting that an algorithm 
from 1987 is valid and potentially 5-10x faster than the 
hungarian method. Sorry for my ignorance in this area, but do 
both algorithms provide optimal solutions, or would there be some 
compromise in quality of the solutions for the Jonker vs 
Hungarian method?