Re: [PATCH v2 01/18] Add a function to solve least-cost assignment problems

Hi Brian,

On Wed, 30 May 2018, brian m. carlson wrote:

On Wed, May 30, 2018 at 09:14:06AM -0700, Stefan Beller wrote:

quoted

Good point. I remember my initial reaction to the file names was
expecting some hungarian notation, which totally didn't make sense, so
I refrained from commenting. Searching the web for the algorithm,
maybe 'lapjv.c' is adequate?  (short for "Linear Assignment Problem
Jonker Volgenant") Matlab has a function named lapjv solving the same
problem, so it would fall in line with the outside world.

Out of interest, why is it called hungarian in the first place? (I
presume that comes from some background of DScho in image processing
or such, so the the answer will be interesting for sure:)

I think it's because tbdiff uses the hungarian Python module, which
implements the Hungarian method, also known as the Kuhn-Munkres
algorithm, for solving the linear assignment problem.  This is the
Jonker-Volgenant algorithm, which solves the same problem.  It's faster,
but less tolerant.

At least this is what I just learned after about ten minutes of
searching.

You learned well.

The Assignment Problem (or "Linear Assignment Problem") is generally
solved by the Hungarian algorithm. I forgot why it is called that way.
Kuhn-Munkres came up with a simplification of the algorithm IIRC but it
still is O(N^4). Then Jonker-Volgenant took a very different approach that
somehow results in O(N^3). It's been *years* since I studied both
implementations, so I cannot really explain what they do, and how the
latter achieves its order-of-magnitude better performance.

And after reading these mails, I agree that the name "hungarian" might be
confusing.

I also think that "lapjv" is confusing. In general, I try to let Matlab
conventions inform on my naming as little as possible, and I find my
naming fu a lot better for it.

So in this case, how about `linear-assignment.c`?

Ciao,
Dscho