Kuhn-Munkres Algorithm (a.k.a. The Hungarian Algorithm)
anonymous
foo at bar.de
Sat Feb 20 07:50:40 UTC 2021
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
More information about the Digitalmars-d
mailing list