In Memoriam: Leonid Khachiyan


Leonid G. Khachiyan of South Brunswick, N.J., professor of computer science at Rutgers, The State University of New Jersey, died suddenly of a heart attack on Friday, April 29 at the age of 52.

"He was among the world's most famous computer scientists," said Haym Hirsh, chair of the computer science department at Rutgers. Khachiyan's fame began in 1979 when Craig Whitney in The New York Times called him, "the mystery author of a new mathematical theorem that has rocked the world of computer analysis." As an obscure mathematician living in Moscow, his discovery first appeared in the Soviet journal, Doklady, little known outside the field and it went unnoticed for months. Western mathematicians first presented his work to a broader audience at the International Mathematical Programming Symposium in 1979 in Montreal.

Khachiyan proved the existence of an efficient way to solve linear programming problems thought to be intractable until that time. His 1979 breakthrough dealt with the underlying mathematics, opening doors beyond linear programming to what is known as combinatorial optimization - finding the best of a finite, but often astronomically large, number of options.

His achievement ultimately untangled serious theoretical roadblocks to designing more advanced methods to attack harder computer problems. Applications today extend to telecommunications, economics, engineering, biology, agriculture and the social sciences.

Khachiyan's 1979 Doklady paper was but his fourth in a long list of single and co-authored publications in diverse areas of algorithms, computational complexity and applications. These include cyclic games on graphs with applications to artificial intelligence; matching; nonlinear programming; extremal covering and inscribed ellipsoids and rounding of polytopes; matrix scaling; complexity of semidefinite programming; interior point methods for structured linear programming; fast approximations for matrix games, for large-scale nonlinear fractional packing and covering, for multicommodity flows and network routing. He also developed efficient algorithms for enumerating all minimal solutions of implicitly stated monotone systems, with applications to minimal transversals in hypergraphs, and to data mining, machine learning, reliability theory, and integer and stochastic programming.

Of Armenian descent, Khachiyan was born on May 3, 1952, 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.

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 has been at Rutgers since 1990. where he held the position of Professor II at the time of his passing.

Khachiyan is survived by his wife of 20 years Olga Pischikova Reynberg and daughters Anna, a sophomore at Rutgers, and Nina, who plans to attend Rutgers in the fall. He is also survived by his father, Genrikh Borisovitsch Khachiyan, a retired professor of theoretical mechanics, his mother, Zhanna Saakovna Khachiyan, a retired civil engineer, and brothers Boris and Eugene Khachiyan, all in Moscow.

Funeral services were held May 3 at Murphy Funeral Home, 616 Ridge Road, Monmouth Junction, (732) 329-2000.

SIAM Optimization Conference Honors

SIAM Activity Group, for the "Optimization 2005" conference, May 15-19, 2005.(Cached)

Additional Press: