We discuss some relevant results obtained by Egerváry in the early Thirties, whose importance has been recognized several years later. We start with a quite well-known historical fact: the first 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őnig (Math Ann 77:453–465, 1916) and Egerváry (Mat Fiz Lapok 38:16–28, 1931) (A recently discovered posthumous paper by Jacobi (1804–1851) contains however a solution method that appears to be equivalent to the Hungarian algorithm). Our second topic concerns a combinatorial optimization problem, independently defined in satellite communication and in scheduling theory, for which the same polynomial-time algorithm was independently published 30 years ago by various authors. It can be shown that such algorithm directly implements another result contained in the same 1931 paper by Egerváry. We finally observe that the latter result also implies the famous Birkhoff-von Neumann theorem on doubly stochastic matrices.

Jenő Egerváry: from the origins of the Hungarian algorithm to satellite communication.

MARTELLO, SILVANO
2010

Abstract

We discuss some relevant results obtained by Egerváry in the early Thirties, whose importance has been recognized several years later. We start with a quite well-known historical fact: the first 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őnig (Math Ann 77:453–465, 1916) and Egerváry (Mat Fiz Lapok 38:16–28, 1931) (A recently discovered posthumous paper by Jacobi (1804–1851) contains however a solution method that appears to be equivalent to the Hungarian algorithm). Our second topic concerns a combinatorial optimization problem, independently defined in satellite communication and in scheduling theory, for which the same polynomial-time algorithm was independently published 30 years ago by various authors. It can be shown that such algorithm directly implements another result contained in the same 1931 paper by Egerváry. We finally observe that the latter result also implies the famous Birkhoff-von Neumann theorem on doubly stochastic matrices.
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11585/84845
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 13
  • ???jsp.display-item.citation.isi??? 8
social impact