A tale of three eras: The discovery and rediscovery of the Hungarian Method

In the Fall of 1953, a translation of a paper of Jenő Egerváry from Hungarian into English combined with a result of Dénes Kőnig provided the basis of a good algorithm for the Linear Assignment Problem. To honor the Hungarian mathematicians whose ideas had been used, it was called the Hungarian Method. In 2005, Francois Ollivier discovered that the posthumous papers of Jacobi contain an algorithm that, when examined carefully, is essentially identical to the Hungarian Method. Since Jacobi died in 1851, this work was done over a hundred years prior to the publication of the Hungarian Method in 1955. This paper will provide an account for the mathematical, academic, social and political worlds of Jacobi, Kőnig, Egerváry, and Kuhn. As sharply different as they were (Prussian monarchy, Hungary under the Nazis and the Communists, and the post-war USA), they produced the same mathematical result. The paper is self-contained, assuming little beyond the duality theory of linear programing. The Hungarian Method and Jacobi’s algorithm will be explained at an elementary level and will be illustrated by an example, solved both by the Hungarian Method and by Jacobi’s Method.