Optimization Community Mourns Loss of Two Linear Programming GiantsJune 10, 2005
George B. Dantzig and Leonid Khachiyan, meeting for the first time, February 1990, Asilomar, California, at the SIAM-organized workshop Progress in Mathematical Programming.
Leonid Khachiyan, a professor of computer science at Rutgers University, died suddenly on April 29, days short of his 53rd birthday. Two weeks later, on May 13, George Dantzig, professor emeritus at Stanford University, died at the age of 90.
Born in Russia (in what is now St. Petersburg), Khachiyan lived for many years in Moscow, where he received doctoral degrees in computational mathematics (1978) and computer science (1984) at the Computing Center of the USSR Academy of Sciences. He emigrated to the U.S. in 1989, becoming a visiting professor at Cornell University's School of Operations Research and Industrial Engineering. He moved to Rutgers in 1990.
As described in a short tribute posted on the Web by the SIAM Activity Group on Optimization, Khachiyan is best known for his use of the ellipsoid algorithm, originally developed for convex programming, to give the first polynomial-time algorithm for the solution of linear programming problems. That work, published in a short paper in the Soviet journal Doklady, came to the attention of linear programming researchers worldwide in 1979, when presented in Montreal at the International Mathematical Programming Symposium. It reached a far wider audience when The New York Times featured Khachiyan and his algorithm in a front-page story.
To put Khachiyan's result in perspective, the SIAG tribute cites the simplex method: "While the simplex algorithm solved linear programs well in practice, Khachiyan gave the first formal proof of an efficient algorithm in the worst case."
Khachiyan's analysis, the piece continues, "led to broad applications of the ellipsoid algorithm as a method for obtaining complexity results for discrete optimization problems. Khachiyan and co-authors also developed polynomial-time algorithms for convex quadratic programming, studied the complexity of polynomial programming over the reals and the integers, and devised the method of inscribed ellipsoids for general convex programming."
A full obituary, recognizing the diversity of the areas in which Khachiyan made substantial contributions, in collaboration with many other researchers, will appear in a future issue of SIAM News.
As to George Dantzig, mention of his name as the developer of the simplex method would have been superfluous in a piece directed to the optimization community---and probably to most readers of SIAM News as well. Dantzig, in fact, is so well known to the optimization community that the editors of SIAM Journal on Optimization, in dedicating the first issue to him, found that they needed very few words: "The first issue of the SIAM Journal on Optimization is dedicated to George Dantzig who has been so influential in the development of optimization." The sad news of Dantzig's death came at press time for this issue of SIAM News; an obituary will appear in a subsequent issue.
B. Curtis Eaves, long-time professor of operations research at Stanford, captured the extent of the loss in a message to friends and colleagues: "George has been with us as if forever, so important for so long. It will take some getting used to, to accept that he is no longer with us. As I have said before, George is the most important, generous, and extraordinary person I have had the privilege of knowing."