Kuhn-Munkres Algorithm (a.k.a. The Hungarian Algorithm)
Sameer Pradhan
pradhan at cemantix.org
Thu Feb 25 20:40:37 UTC 2021
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?
More information about the Digitalmars-d
mailing list