Kuhn-Munkres Algorithm (a.k.a. The Hungarian Algorithm)
anonymous
foo at bar.com
Thu Feb 25 21:52:58 UTC 2021
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.
More information about the Digitalmars-d
mailing list