Published in:
Harold W. Kuhn, in his celebrated paper entitled `The Hungarian
Method for the assignment problem', [Naval Research Logistic
Quarterly, 2 (1955), pp. 83-97] described an algorithm for
constructing a maximum weight perfect matching in a bipartite graph.
In his delightful reminescences [18], Kuhn explained how the
works (from 1931) of two Hungarian mathematicians, D. Konig and
E. Egerváry, had contributed to the invention of his algorithm, the
reason why he named it the Hungarian Method. (For citations from
Kuhn's account as well as for other invaluable historical notes on the
subject, see A. Schrijver's monumental book [20].)
In this note I wish to pay tribute to Professor H.W. Kuhn by
exhibiting the exact ralationship between his Hungarian Method and
the achievements of Konig and Egerváry, and by outlining
the fundamental influence of his algorithm on Combinatorial
Optimization where it became the prototype of a great number of
algorithms in areas such as network flows, matroids, and matching
theory. And finally, as a Hungarian, I would also like to
illustrate that not only did Kuhn make use of ideas of Hungarian
mathematicians, but his extremely elegant method has had a great
impact on the work of a next generation of Hungarian researchers.
Bibtex entry:
AUTHOR | = | {Frank, Andr{\'a}s}, |
TITLE | = | {On Kuhn's Hungarian Method - a tribute from Hungary}, |
NOTE | = | {{\tt egres.elte.hu}}, |
INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
YEAR | = | {2004}, |
NUMBER | = | {TR-2004-14} |