From: brian m. carlson <sandals@crustytoothpaste.net>
Date: Wed, 30 May 2018 23:28:38 GMT
Subject: Re: [PATCH v2 01/18] Add a function to solve least-cost assignment problems
Message-ID: <20180530232837.GD671367@genre.crustytoothpaste.net>
In-Reply-To: <CAGZ79kZ77qBuSDGBJa5b1AvKLBSOOnTad_UXm9EP0aJSrmEohw@mail.gmail.com>

On Wed, May 30, 2018 at 09:14:06AM -0700, Stefan Beller wrote:
> 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.
-- 
brian m. carlson: Houston, Texas, US
OpenPGP: https://keybase.io/bk2204