Leonid Khachiyan

Leonid Khachiyan (May 3, 1952 - April 29, 2005) was a Russian-born mathematician who taught Computer Science at Rutgers University. He was most famous for his Ellipsoid algorithm for linear programming, which was the first such algorithm known to have a polynomial running time. Even though this algorithm was shown to be impractical due to the high degree of the polynomial in its running time, it has inspired other randomized algorithms for convex programming and is considered a significant theoretical breakthrough. Faculty photo of Leonid Khachiyan File links The following pages link to this file: Leonid Khachiyan ... 1952 - Wikipedia /**/ @import /skins/monobook/IE50Fixes. ... 2005 is a common year starting on Saturday of the Gregorian calendar. ... The Russian Federation (Russian: Росси́йская Федера́ция, transliteration: Rossiyskaya Federatsiya or Rossijskaja Federacija), or Russia (Russian: Росси́я, transliteration: Rossiya or Rossija), is a country that stretches over a vast expanse of eastern Europe and northern Asia. ... A mathematician is a person whose area of study and research is mathematics. ... Rutgers University Rutgers, The State University of New Jersey, is located in New Brunswick, Piscataway, Camden and Newark, New Jersey. ... In mathematics, linear programming (LP) problems are optimization problems in which the objective function and the constraints are all linear. ... This article is about the term degree as used in mathematics. ... In mathematics, polynomial functions, or polynomials, are an important class of simple and smooth functions. ... A randomized algorithm is an algorithm which is allowed to flip a truly random coin. ...

Of Armenian descent, Khachiyan was born in St. Petersburg and moved to Moscow with his parents at age 9 where he later earned a Ph.D. in computational mathematics in 1978 and a D.Sc. in computer science in 1984, both from the Computing Center of the USSR Academy of Sciences. In 1982 he won the prestigious Fulkerson Prize from the Mathematical Programming Society and the American Mathematical Society for outstanding papers in the area of discrete mathematics. Russian Academy of Sciences (Росси́йская Акаде́мия Нау́к) is the national academy of Russia. ... The Fulkerson Prize for outstanding papers in the area of discrete mathematics is sponsored jointly by the Mathematical Programming Society (MPS) and the American Mathematical Society (AMS). ... The American Mathematical Society (AMS) is dedicated to the interests of mathematical research and education, which it does with various publications and conferences as well as annual monetary awards to mathematicians. ...

Prior to coming to the United States in 1989, Khachiyan held a series of research and teaching positions at the Computing Center of the USSR Academy of Sciences and the Moscow Institute of Physics and Technology. In 1989 he joined Cornell University’s School of Operations Research and Industrial Engineering as a visiting professor and had been at Rutgers since 1990. Moscow Institute of Physics and Technology (Phystech, MIPT) is one of the better known Russian universities, sometimes referred to as the Russian MIT. The Institutes primary facilities are located in Dolgoprudny, Moscows satellite town. ... Cornell University is a private university located in Ithaca, New York, USA, and a member of the Ivy League. ...

Khachiyan is survived by his wife of 20 years and two daughters. He is also survived by his father, a retired professor of theoretical mechanics, his mother, a retired civil engineer, and two brothers, all who live in Moscow.

George Dantzig and Leonid Khachiyan