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

作者：Kuhn Harold W^*

来源：European Journal of Operational Research, 2012, 219(3): 641-651.

DOI：10.1016/j.ejor.2011.11.008

• Assignment
• Combinatorial optimization
• Graph theory
• Linear programming
• Hungarian Method

In the Fall of 1953, a translation of a paper of Jeno Egervary from Hungarian into English combined with a result of Denes Konig 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 of the mathematical, academic, social and political worlds of Jacobi, Konig, Egervary, 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 programming. 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.

• 出版日期2012-6-16