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

[anonymous]

On Thursday, 25 February 2021 at 20:40:37 UTC, Sameer Pradhan 
wrote:
> 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?

well, there are at least 3 approaches to the linear assignment 
problem
1) the hungarian method (from the 1950s)
2) Jonker / Volgenant algorithm
3) reduction to min-cost flow. There are several algorithms for 
min-cost flow. One of them is the network simplex method.

all are exact, i.e. return solutions with the same 
costs/objective value. Note that there might be more than one 
optimal solution.

In theory one could also use a general purpose LP solver (any 
basic solution will be integer), but even the (expensive) 
commercial packages are slower than a reasonable implementation 
of the 3 approaches above.

As mentioned before, I have no practical experience with 2) as 
the license terms of the original Pascal implementation in  the 
paper are somewhat unclear (and therefore of all literal 
translations to other programming languages).
The 5-10x speedup is between a reasonable (school-bookish) 
implementation of the hungarian method I can not share and 
lemon::NetworkSimplex (-> option 3) - but lemon is a template 
heavy C++ library, so interfacing it to D will require some C++ 
programming.