Blog

kuniga.me > NP-Incompleteness

NP-Incompleteness

Most recent post:

The Hungarian Algorithm

02 Dec 2022

Harold W. Kuhn thumbnail

Harold William Kuhn was an American mathematician, known for the Karush–Kuhn–Tucker conditions and the Hungarian method for the assignment problem [1].

According to Wikipedia [2], Kuhn named the algorithm Hungarian method because it was largely based on the earlier works of Hungarian mathematicians Dénes Kőnig and Jenő Egerváry.

However in 2006, the mathematician Francois Ollivier found out that Carl Jacobi (known for Jacobian matrices) had already developed a similar algorithm in the 19th century in the context of systems of differential equations and emailed Kuhn about it [6].

One fascinating coincidence is that Jacobi is Kuhn’s ancestral advisor according to the Mathematics Genealogy Project! [5]. Here’s the ancestry chain (year when they got their PhD in parenthesis):

If this genealogy is to be trusted, I wonder if Kuhn was aware of this fact, given he wrote about Jacobi’s life in [6].

In this post we’ll explore this algorithm and provide an implementation in Python.

Continue reading...

Sub-pages

Older Posts