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

[Hoyt Koepke]

>> Well, the hungarian algorithm has a theoretical upper bound of O(n^3),
>> with n being the number of nodes, which is pretty much the best you
>> can do if you have a dense graph and make no assumptions on
>> capacities.
>
> OK, your input is making my motivation to fight with Jonker-Volgenant go
> down. I'll see with the other people involved if we still target
> Jonger-Volgenant, or if we stick with the hungarian algorithm, in which
> case the problem is solved.

I'd do that route. From my (somewhat anecdotal) observations, a well
coded version of the Hungarian algorithm will beat moderately
well-coded implementations of other algorithms on most common types of
problems; the data structures in other algorithms are harder to get
right.  Also, they often tend to show their strengths only on
sufficiently large problems.  I'd guess that for a speed up, your time
would be better spent profiling and maybe cythoning your current
implementation of the Hungarian algorithm (also note that there's a
few bsd/mit C++ implementations floating around, check the wikipedia
page).

>
>> Hope that answers your questions :-).
>
> It does. Thanks a lot, it is very useful to have expert knowledge
> available.

Well, I don't know if I'm an "expert" in this area, but I rub
shoulders with a few and I'm glad to be of help.

-- Hoyt

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