Leonid Khachiyan

Leonid Khachiyan

Leonid Genrikhovich Khachiyan (Armenian: Լեոնիդ Գենրիխովիչ Խաչիյան; Russian: Леонид Генрихович Хачиян; May 3, 1952 – April 29, 2005) was a Soviet mathematician of Armenian descent who taught Computer Science at Rutgers University. He was most famous for his ellipsoid algorithm (1979) 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.

Biography

Khachiyan was born in St. Petersburg and moved to Moscow with his parents at age 9. There 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.

Prior to moving 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.

After moving to the United States, Khachiyan's work continued some of its old ideas, as he worked on the complexity of maximal volume inscribed ellipsoids and wrote a paper on rounding polytopes, adding some new ones. He wrote a series of papers with Bahman Kalantari on various matrix scaling and balancing problems.

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



This article is issued from Wikipedia - version of the 11/27/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.