Megiddo earns von Neumann Theory Prize

David Shmoys (left), joined by INFORMS President Steve Robinson (center), presents the John von Neumann Theory Prize to Nimrod Megiddo (right) of IBM.

David Shmoys (left), joined by INFORMS President Steve Robinson (center), presents the John von Neumann Theory Prize to Nimrod Megiddo (right) of IBM.

The 2014 John von Neumann Theory Prize of INFORMS was awarded to Nimrod Megiddo, a research scientist at the IBM Almaden Research Center in San Jose, Calif., for his “fundamental contributions across a broad range of areas of operations research and management science, most notably in linear programming, combinatorial optimization and algorithmic game theory.”

Prize Committee member David Shmoys, on behalf of Committee Chair Paul Glasserman, made the presentation at the INFORMS Award Ceremony held in conjunction with the INFORMS Annual Meeting in San Francisco.

The prize recognizes scholars who have made fundamental, sustained contributions to theory in operations research and the management sciences.

The award citation read in part:

Of all of the areas in which he has worked, Megiddo has had perhaps the most profound impact on the theory of linear programming. His work on the probabilistic analysis of the simplex method, alone and with Adler, established some of the most important results in the area, including the best (quadratic) bound for the complexity of a complete parametric pivoting method and an explanation of why this is possible for the lexicographic version but not the standard Lemke perturbation. He also established a quadratic lower bound for this method. This, along with work of Smale, Borgwardt and Haimovich, together with independent proofs of the quadratic result by Adler-Karp-Shamir and Todd, provided the first theoretical justification for the success of the simplex method.

Megiddo was an early leader in the theory of interior-point methods, and he laid the framework for the development of primal-dual methods in his seminal paper on pathways to the solution. This paper was the foundation for the hugely successful primal-dual interior-point methodology for linear programming, implementations of which are now included in every serious software package. His contributions to interior-point methods culminated in his work on the linear complementarity problem with Kojima and Noma.

Megiddo’s work has also played a role in highlighting the question, still unresolved today, of whether there is a strongly polynomial algorithm for linear programming. Megiddo made two strikingly beautiful contributions in the design of strongly polynomial algorithms: his innovative multi-dimensional searching technique that yielded a strongly polynomial algorithm for linear programming in constant dimensions, and its forerunner in parametric search algorithms, which showed how to leverage an algorithm to optimize a linear objective into a corresponding strongly polynomial algorithm to optimize a rational objective function over the same feasible region.

In algorithmic game theory, Megiddo has done groundbreaking work that anticipated by two decades the more recent blossoming of the field. In particular, Megiddo raised the question of the complexity of equilibrium computation in the 1980s and showed that the usual notion of NP-hardness is not adequate to capture the apparent difficulty of the problem, anticipating and opening the way to subsequent developments in the area. On the algorithmic side, his later work (with Kholler and von Stengel) also showed how equilibrium solutions for two-person games can be computed in polynomial time, even if the game were given in extensive form. Bridging between concepts in game theory and traditional combinatorial optimization, Megiddo initiated the investigation of computing fair flows in networks, and did path-setting work on efficient algorithms to compute the fair allocation of costs in a number of game-theoretic settings.

His work has been highly influential, in both identifying key concepts and in developing new algorithmic approaches for fundamental problems.