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

Gael Varoquaux gael.varoquaux at normalesup.org
Mon May 16 12:28:51 EDT 2011


On Mon, May 16, 2011 at 09:15:21AM -0700, Hoyt Koepke wrote:
> > 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.

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. 

> It's a little slower on large graphs, but it still is pretty quick.

Can you put any numbers on the difference, or rule of thumbs? Is there an
algorithmic complexity difference? If so, what kind of dependency are we
talking about? Is it only in the prefactors?

Sorry for drowning you with questions, but linear programming has always
seem a dark craft to me, due to my lack of training on these issues.

Cheers,

Gael



More information about the NumPy-Discussion mailing list