Faculty of Engineering and Computer Science
Harold W. Kuhn
Department of Mathematics
THE HUNGARIAN METHOD FOR THE ASSIGNMENT PROBLEM
AND HOW JACOBI BEAT ME BY 100 YEARS
This lecture is self-contained and presumes no prior knowledge of the
algorithm known as the "Hungarian Method".
The algorithm will be developed in the lecture and some recent results
discussed. Finally, the unknown work of Jacobi
of 150 years ago will be described and compared with the results of König,
Egerváry, and Kuhn.
Tuesday 12 September 6:00 PM
Engineering, Computer Science, and Visual Arts Complex (EV)
2.260 / 2.238 / 2.204
1515 Ste-Catherine West
From the citation for the 1980 John
von Neumann Theory Prize:
Presentation of the 1980 von Neumann Prize for Theory jointly to David
Gale, Harold W. Kuhn, and Albert W. Tucker will come as no surprise to
those familiar with their contributions to the theory of
optimization. Their research played a seminal role in laying the
foundations of game theory, linear and non-linear programming -- work
that continues to be of fundamental importance to modern operations
research and management science.
The early research of the founders of the 'Princeton School,'
concerned the mathematical theory of linear inequalities as applied to
linear programs, matrix games, the now-classical formulations of
symmetric games, games in extensive form, n-person games, games of
perfect recall, and the value of information. The list of their
accomplishments, not to mention distinguished students and
collaborators, is too long to present in detail. Pure mathematics
played a strong role in their research. Topological notions such as
homotopic and fixed point methods, first introduced by Tucker, now
find among their many and wide applications the recent work of Kuhn
for computing optima and equilibria; they are used by Gale in his
studies of games of connectivity. The surprising association between
combinatorics and continuous variable optimization was exhibited by
Kuhn in his well-known Hungarian method for solving the assignment
problem. The idea of duality, while properly credited to von Neumann,
was developed independently by them. The famous Kuhn-Tucker Conditions
play a fundamental role in non-linear programming. ...