[Numpy-discussion] Linear assignment problem: Jonker-Volgenant algorithm

Hoyt Koepke 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

++++++++++++++++++++++++++++++++++++++++++++++++
+ Hoyt Koepke
+ University of Washington Department of Statistics
+ http://www.stat.washington.edu/~hoytak/
+ hoytak at gmail.com
++++++++++++++++++++++++++++++++++++++++++



More information about the NumPy-Discussion mailing list