Leonid Khachiyan

From Wikipedia, the free encyclopedia

Leonid Genrikhovich Khachiyan (Armenian: Լեոնիդ Գենրիխովիչ Խաչիյան; Russian: Леонид Генрихович Хачиян; May 3, 1952 – April 29, 2005) was a Armenian 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.

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 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.

After coming to the States, Khachiyan's work continued some of its old themes, like his work on the complexity of maximal volume inscribed ellipsoids and his fascinating paper on rounding polytopes, and added 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. 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.