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

[Gael Varoquaux]

On Mon, May 16, 2011 at 10:03:09AM -0700, Hoyt Koepke wrote:
> > I might go that way: I already have pure-Python code that implements it
> > and that I have been using for a year or so.

> Fair enough -- though you'd probably get a big speed up moving to cython.

Indeed. If this is needed, we'll consider it.

> 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.

> Hope that answers your questions :-).

It does. Thanks a lot, it is very useful to have expert knowledge
available.

Gael