TR-2004-14

On Kuhn's Hungarian Method - a tribute from Hungary

András Frank

Published in:
Naval Research & Logistics. 52 (2005) 2-5.



Abstract

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:

@techreport{egres-04-14,
AUTHOR = {Frank, Andr{\'a}s},
TITLE = {On Kuhn's Hungarian Method - a tribute from Hungary},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2004},
NUMBER = {TR-2004-14}
}


Last modification: 5.12.2018. Please email your comments to Tamás Király!