Jenö Egerváry: from the origins of the Hungarian algorithm

Technical Report OR-09-1 DEIS, Universit a di Bologna Viale Risorgimento 2 40136 Bologna, Italy Noname manuscript No. (will be inserted by the editor) Jen}o Egerv ary: from the origins of the Hungarian algorithm to satellite communication Silvano Martello DEIS, University of Bologna, Bologna, Italy. e-mail: silvano.martello@unibo.it The date of receipt and acceptance will be inserted by the editor Abstract We discuss some

relevant results obtained by Egerv ary in the early Thirties, whose importance has been recognized several years later. We start with a quite well-known historical fact: the rst modern polynomial- time algorithm for the assignment problem, invented by Harold W. Kuhn half a century ago, was christened the Hungarian method" to highlight that it derives from two older results, by K}onig (1916) and Egerv ary (1931). (A recently discovered posthumous paper by Jacobi (1804-1851) contains how- ever a solution method that appears to be equivalent to the Hungarian algorithm.) Our second topic concerns a combinatorial optimization prob- lem, independently de ned in satellite communication and in scheduling theory, for which the same polynomial-time algorithm was independently published thirty years ago by various authors. It can be shown that such algorithm directly implements another result contained in the same 1931 paper by Egerv ary. We nally observe that the latter result also implies the famous Birkho -von Neumann theorem on doubly stochastic matrices. Key words Assignment problem, Hungarian algorithm, Open shop sched- uling, Satellite switched time division multiple access 1 Introduction This paper is devoted to a discussion on the implications of a paper that was published in Hungarian by Jen}o Egerv ary [6] in 1931, and was ignored for many years by the international mathematical community. The paper, translated into English by Harold W. Kuhn [20] in 1955, basically consists of two theorems. The rst one is a cornerstone of the famous Hungarian method" for the assignment problem. The proof of the second (much less 2 S. Martello known) theorem provides a polynomial-time algorithm for a combinatorial optimization problem that was independently established in the Seventies in two di erent domains, for which di erent authors proposed solution al- gorithms that replicate the one de ned by Egerv ary. In addition, an easy extension of the second theorem to non-negative real matrices contains as a special case the celebrated Birkho {von Neumann theorem, that was pub- lished in Spanish by Garrett Birkho [1] in 1946 and for which John von Neumann [37] gave in 1953 an elegant elementary proof. In Section 2 we recall the early years of the assignment problem and the contributions of the Hungarian mathematicians. More details on these exciting events can be found in Kuhn [22], Schrijver [32] (Chapter 17), Frank [8], J uttner [18], Schrijver [33] and Burkard, Dell’Amico and Martello [2] (Chapters 2{4). We...

Website: www.or.deis.unibo.it | Filesize: -
No of Page(s): 14
Download Jenö Egerváry: from the origins of the Hungarian algorithm to ....pdf