Past Awards
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 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 80’s and showed that the usual notion of NPhardness 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 2-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.
In summary, Nimrod Megiddo has made 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. His work has been highly influential, in both identifying key concepts and in developing new algorithmic approaches for fundamental problems.
Acceptance Remarks
Being awarded the John von Neumann Theory Prize is truly one of the greatest moments of my professional life. I am greatly honored having my name added to the impressive list of past winners of this prize, and I thank the members of the committee for selecting me. Each of the names of George Dantzig, Richard Bellman, Herbert Simon, Kenneth Arrow, Robert Aumann, Lloyd Shapley, David Gale, David Blackwell, Ralph Gomory, Egon Balas, Alan Hoffman, Philip Wolfe, Herbert Scarf, Richard Karp, Pete Veinott and László Lovász means a lot to me, and this is only a part of list.
I am very grateful to all of my wonderful colleagues for our friendship and collaboration, and for teaching, inspiring and encouraging me over the years. Without them I would not have reached this joyful moment.
Thanks to Robert Aumann and Michael Maschler for teaching me game theory at the Einstein Institute of Mathematics of the Hebrew University of Jerusalem. From them I learned the foundational contributions to game theory by Nash, Shapley, Gale, Kuhn, Lemke, and Scarf. I also heard of Balinski's work in Micha Perles' course on convex polytopes.
After I had gotten my Masters from the Hebrew University, I spent several years with the Israeli Defense Forces in an O.R. group, where I was introduced for the first time to Operations Research by Adam Shefi and Roni Einav. At that time I started attending the meetings of ORSIS, the O.R. Society of Israel. George Dantzig was invited to one of those meetings. I also heard at that time about Bellman and Balas. While working on truly applied projects, I also worked on my Ph.D. thesis in theoretical game theory.
Near the end of my military service, I started to teach O.R. courses in the statistics department of Tel Aviv University. I had to study a lot of material before I could teach it. As a result, I became acquainted with the names of Kuhn, Tucker, and Gomory. I also heard from my colleagues in statistics about Blackwell. In Tel Aviv I first met Ehud Kalai, to whom I am very grateful for our collaboration in Tel Aviv and later at the Kellogg school, where I met many great game theorists and economists.
While at Tel Aviv University, I was very lucky to get a fellowship to visit Japan, where I spent almost one year. In Japan I first met Masakazu Kojima, from whom I learned a lot about complementarity and fixed-points. I am very thankful to Kojima for the year in Japan and for our extensive collaboration later when he and his students visited me at IBM during several summers. Our joint work on interior-point methods was recognized by the Lanchester Prize and the INFORMS Computing Society Prize.
I am very thankful to George Dantzig for more than thirty years of friendship and intellectual interaction. He first invited me for a visit to Stanford, where I met and befriended Pete Veinott, Dick Cottle and Curtis Eaves. Several years later, Dantzig arranged for me a longer visit to Stanford to work with Donald Knuth. That turned out to be one of my most productive years.
Thanks to my friend and colleague Eitan Zemel, whom I first met at the Kellogg school. We continued to collaborate over many years both at Kellogg and at Tel Aviv.
Special thanks to my friends and colleagues at Tel Aviv University, Arie Tamir, Refael Hassin and Zvi Galil, with each of whom I collaborated on many projects and learned a lot. Zvi introduced me to computational complexity, Arik taught me many topics in O.R., and with Rafi I had many inspiring discussions.
Thanks to Egon Balas and Gérard Cornuéjols with whom I spent a wonderful sabbatical at the Tepper School of Carnegie-Mellon University.
Thanks to my friend and colleague of many years Ilan Adler, with whom I had countless discussions on many topics, and very successful research into the probabilistic analysis of the simplex method.
Thanks to all of my colleagues at the IBM Research Division, where I have worked longer than any other place. Many thanks to Edith Cohen for work on parametric searching, to Daphne Koller for work on computational game theory, to Shinji Mizuno, Takashi Tsuchiya and Akiko Yoshise for work on interior-point methods, to Miklos Ajtai and Noga Alon for work on low-dimensional linear programming, and to Daniela de Farias and Elad Hazan for work in machine learning. With each of them I had an excellent research experience during my years at IBM.
IBM Research had several extremely bright past recipients of this prize: Alan Hoffman and Philip Wolfe, and Ralph Gomory who was the Director of Research when I was hired. Also, Richard Karp and Ellis Johnson worked there for many years before receiving this prize. I am very pleased to follow in their footsteps.
Thank you all.
The 1992 Frederick W. Lanchester Prize was awarded to a group of five authors who have worked collectively on a long-term research program aimed at establishing a theoretical foundation for primal-dual interior point methods for linear programming and its generalization to linear complementarity problems.
The authors Masakazu Kojima and Toshihito Noma of the Tokyo Institute of Technology, Nimrod Megiddo of the IBM Almaden Research Center in San Jose, Calif., Shinji Mizuno of Wuerzburg University in Germany, and Akiko Yoshise of the University of TsuLuba in Japan were recognized for a collection of 11 articles, including the monograph entitled A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems, which appeared in Lecture Notes in Computer Science, published by Springer Verlag in 1991. The other papers were:
- N. Megiddo (1989) "Pathways to the Optimal Set in Linear Programming", in: N. Megiddo, ed., Progress in Mathematical Programming: Interior Point and Related Methods, Springer-Verlag, New York) 131-158.
- M. Kojima, S. Mizuno and A. Yoshise (1989) "A Primal-Dual Interior Point Algorithm for Linear Programming", in: N. Megiddo, ed., Progress in Mathematical Programming: Interior Point and Related Methods (Springer-Verlag, New York) 29-47.
- M. Kojima, S. Mizuno and A. Yoshise (1989) "A Polynomial-Time Algorithm for a Class of Linear Complementarity Problems", Mathematical Programming, Vol.44, 1-26.
- M. Kojima, S. Mizuno and A. Yoshise (1991) "An O(sqrt{n}) Iteration Potential Reduction Algorithm for Linear Complementarity Problems", Mathematical Programming, Vol. 50, 331-342.
- M. Kojima, N. Megiddo, T. Noma and A. Yoshise (1991) "A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems", Lecture Notes in Computer Science, Vol. 538, Springer-Verlag.
- M. Kojima, N. Megiddo and S. Mizuno (1993) "Theoretical Convergence of Large-Step Primal-Dual Interior Point Algorithms for Linear Programming", Mathematical Programming, Vol. 59, 1-22.
- M. Kojima, N. Megiddo and S. Mizuno (1993) "A Primal-Dual Infeasible-Interior-Point Algorithm for Linear Programming", Mathematical Programming, Vol. 61, 263-280.
- N. Megiddo (1991) "On Finding Primal- and Dual-Pptimal bases", ORSA Journal on Computing, Vol.3, 63-65.
- M. Kojima, S. Mizuno and T, Noma (1989) "A New Continuation Method for Complementarity Problems with Uniform P-Functions", Mathematical Programming, Vol.43, 107-113.
- M. Kojima, N. Megiddo and S. Mizuno (1993) "A General Framework of Continuation Methods for Complementarity Problems", Mathematics of Operations Research, Vol. 18, 945-963.
- M. Kojima, N. Megiddo and T. Noma (1991) "Homotopy Continuation Methods for onlinear Complementarity Problems", Mathematics of Operations Research, Vol. 16, 754-774.
The citation says, in part, that their "... research has been at the forefront of the very extensive literature on interior point algorithms, which originated with the method of Karmarkar. While their work is mostly theoretical and motivated by complexity issues, it applies to practical algorithms of great economic significance in the solution of a very large-scale LP problems.
"In particular, their monograph not only provides a unified treatment of several important algorithms for the LCP, but also introduces a new matrix class important for such problems. The work is a tour de force in both the generality and power of the results and covers a very wide range of algorithms and problems; in addition, the exposition is excellent."