[Numpy-discussion] Linear assignment problem: Jonker-Volgenant algorithm
hoytak at stat.washington.edu
Mon May 16 12:15:21 EDT 2011
In this case, lemon exists only as C++ header files, with no compiled
code. A few cython functions should make it pretty simple. However,
yeah, it is a bit heavyweight.
> Thanks for the suggestion. Unfortunately, I do not want to add compiled
> code (or an external dependency) to the scikit for this solver, as it is
> a fairly minor step for us. I particular chances are that it will never
> be a computational bottleneck on our poblems.
If that's the case, I suggest just using the Hungarian algorithm.
It's a little slower on large graphs, but it still is pretty quick.
And there's tons of implementations out there, as it's often a
standard coding project in undergrad algorithms courses.
http://en.wikipedia.org/wiki/Hungarian_algorithm has links to a few.
+ Hoyt Koepke
+ University of Washington Department of Statistics
+ hoytak at gmail.com
More information about the NumPy-Discussion