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

Harold W. Kuhn

European Journal of Operational Research, 2012, vol. 219, issue 3, 641-651

Abstract: 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.

Keywords: Assignment; Combinatorial optimization; Graph theory; Linear programing; Hungarian Method (search for similar items in EconPapers)
Date: 2012
References: Add references at CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221711009957
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:219:y:2012:i:3:p:641-651

DOI: 10.1016/j.ejor.2011.11.008

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().