Re: [PATCH v2 01/18] Add a function to solve least-cost assignment problems
- From
brian m. carlson <sandals@crustytoothpaste.net>
- Date
- May 30, 2018, 23:28 UTC
- 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:
Show 10 quoted lines
> 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