"Reflections on a Favorite Child"

Biography:

Dr. Kuhn's fields of research include linear and nonlinear programming, the theory of games, combinatorial problems and the application of mathematical techniques to economics. Among his scholarly publications, specifically noteworthy are his work on nonlinear programming (joint with A.W. Tucker, 1950) and on the Hungarian Method for the Assignment Problem (1955).

His honors include the John von Neumann Theory Prize of the Operation Research Society of America (jointly with David Gale and A.W. Tucker), the Guggenheim Fellowship, and Fellow of the American Academy of Arts and Science.

His recent activities have been centered on game theory. At the Nobel Awards ceremonies in Stockholm in 1994, he chaired a seminar on "The Work of John Nash in Game Theory," and in 2002 he co-edited the famous book "The Essential John Nash."

Abstract:

Fifty five years ago, two results of the Hungarian mathematicians, Koenig and Egervary, were combined using the duality theory of linear programming to construct the Hungarian Method for the Assignment Problem. In a recent reexamination of the geometric interpretation of the algorithm (proposed by Schmid in 1978) as a steepest descent method, several variations on the algorithm have been uncovered, which seem to deserve further study.

The lecture will be self-contained, assuming little beyond the duality theory of linear programming. The Hungarian Method will be explained at an elementary level and will be illustrated by several examples.

We shall conclude with account of a posthumous paper of Jacobi containing an algorithm developed by him prior to 1851 that is essentially identical to the Hungarian Method, thus anticipating the results of Koenig (1931), Egervary (1931), and Kuhn (1955) by many decades.