On Kuhn's Hungarian Method – A tribute from Hungary

On Kuhn’s Hungarian Method – A tribute from Hungary Andr´as Frank October 2004 EGRES Technical Report No. 2004-14 1 On Kuhn’s Hungarian Method – A tribute from Hungary Andr´as Frankstar Harold W. Kuhn, in his celebrated paper entitled The Hungarian Method for the as- signment 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. K˝onig and E. Egerv´ary, 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 ex- act ralationship between his Hungarian Method and the achievements of K˝onig and Egerv´ary, and by outlining the fundamental influence of his algorithm on Combina- torial 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. 1 Relationships A little technicality: though both Egerv´ary and Kuhn used matrix terminology, here I follow K˝onig by working with the equivalent bipartite graph formulation. Let us start with a quotation from Kuhn’s paper [17]: ‘One interesting aspect of the algorithm is the fact that it is latent in the work of D. K¨onig and E. Egerv´ary that predates the birth of linear programming by more than 15 years (hence the name of Hungarian Method)’. But what is the exact relationship of the algorithm arising from Egerv´ary’s proof technique and Kuhn’s method? In a paper [11], written in Hungarian, I exhibited in detail the achievements of K˝onig and Egerv´ary and Kuhn. The following section is an outline of some observations from [11]. starSupported by the Hungarian National Foundation for Scientific Research, Grant Number OTKA T037547, and by European MCRTN ADONET, Grant Number 504438. Department of Operations Research, E¨otv¨os University, P´azm´any P. s. 1/c, Budapest, Hungary, H-1117 and Traffic Lab Ericsson Hungary, Laborc u.1, Budapest, Hungary H-1037. MTA-ELTE Egerv´ary Research Group. e-mail: frank@cs.elte.hu October 2004 1.1 K˝onig’s theorem and proof method 2 1.1 K˝onig’s theorem and proof method The starting point is K˝onig’s matching theorem. Theorem 1.1 (K˝onig). In a bipartite graph G = (S,T;E), the maximum cardinality ν = ν(G) of a matching is equal to the minimum number...

Website: www.cs.elte.hu | Filesize: -
No of Page(s): 8
Download On Kuhn's Hungarian Method – A tribute from Hungary.pdf