Improvements in InteriorPoint Methods
Mathematics Accomplishment  1988  1998
IBM researcher: Nimrod Megiddo
Where the work was done: IBM Almaden Research Center
What we accomplished: Interiorpoint methods are used to solve many optimization problems, and hence efficient techniques are important in achieving good results in practical systems. The numerous improvements from Nimrod Megiddo have done that, and were recognized with the 2014 John von Neumann Theory Prize of INFORMS, the 1992 Frederick W. Lanchester Prize of INFORMS for the outstanding paper in operations research, and the 1992 INFORMS Computer Society Prize. According to S. Wright's book "PrimalDual InteriorPoint Methods," Megiddo's paper "Pathways to the optimal set in linear programming" is "possibly the most influential paper . . . which many regard as the cornerstone for the field of primaldual algorithms."
Related links: From Nimrod Megiddo's website:
 Books
 M. Kojima, N. Megiddo, T. Noma and A. Yoshise, "A unified approach to interior point algorithms for linear complementarity problems," Lecture Notes in Computer Science 538, SpringerVerlag, 1991.
 N. Megiddo, Progress in Mathematical Programming: InteriorPoint and Related Methods (edited), SpringerVerlag, New York, 1988

Journal Articles Book Chapters

N. Megiddo, "Pathways to the optimal set in linear programming" in: Progress in Mathematical Programming: InteriorPoint and Related Methods (N. Megiddo, Ed.) SpringerVerlag, New York, 1988, pp. 131158.

N. Megiddo and M. Shub, "Boundary behavior of interior point algorithms in linear programming," Mathematics of Operations Research 14 (1989), No. 1, 97146.

M. Kojima, N. Megiddo, T. Noma and A. Yoshise, "A unified approach to interior point algorithms for linear complementarity problems: A summary," Operations Research Letters 10 (1991) 247254.

N. Megiddo, "On finding primal and dualoptimal bases" ORSA Journal of Computing 3 (1991) 6365.

M. Kojima, N. Megiddo and Y. Ye, "An interior point potential reduction algorithm for the linear complementarity problem," Mathematical Programming 54 (1992), No. 3, 267279.

M. Kojima, N. Megiddo and S. Mizuno, "Theoretical convergence of largestep primaldual interior point algorithms for linear programming," Mathematical Programming 59 (1993) 122.

M. Kojima, N. Megiddo and S. Mizuno, "A primaldual infeasibleinteriorpoint algorithm for linear programming," Mathematical Programming 61 (1993) 263280.

N. Megiddo, S. Mizuno, and T. Tsuchiya, "A modified layeredstep interiorpoint algorithm for Linear Programming," Mathematical Programming 82 (1998), No. 3, 339355.

BACK TO IBM RESEARCH ACCOMPLISHMENTS