By RICK MALWITZ
STAFF WRITER

RUTGERS -- Leonid G. Khachiyan of South Brunswick, a Rutgers University professor of computer science whose work in his native Soviet Union in 1979 "rocked the world of computer analysis," died Friday of a heart attack.

His funeral was held yesterday on what would have been his 53rd birthday.

"He was among the world's most famous computer scientists," said Haym Hirsh, chairman of the computer science department at Rutgers, where Khachiyan had taught since 1990.

"He was a mathematical dynamo," said Michael Todd, a computer science professor at Cornell University, where Khachiyan taught prior to joining the Rutgers faculty. "He was cynical about politics, loyal to his friends, a nice person to know."

His 1979 breakthrough work, "The Polynomial Algorithm in Linear Programming," paved the way for computer scientists to solve problems with a large number of variables through the use of computational optimization, a process that finds the most efficient solution from among a finite, but often astronomically large, number of options.

It is the process, for example, that airlines use to create flight schedules.

"Efficient scheduling is one way airlines have been able to keep passenger costs down, despite higher fuel prices and increased labor costs," Todd explained.

Applications of combinatorial optimization are used today in telecommunications, economics, engineering, biology, agriculture and the social sciences.

Khachiyan, of Armenian descent, was born in Leningrad in 1952, and moved to Moscow with his parents at age 9.

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

His 1979 discovery was published in a Soviet journal, Doklady, and received little notice until it was presented by Western mathematicians at the International Mathematical Programming Symposium in Montreal in 1979.

On Nov. 27, 1979, his story was told by The New York Times under the headline, "Soviet Mathematician is Obscure No More," referring to him as "The mystery author of a new mathematical theorem that has rocked the world of computer analysis."

"The dark-haired bachelor says he was "somewhat surprised' by the enthusiastic response in the West to his paper," wrote reporter Craig Whitney.

George Dantzig of Stanford University told The New York Times that following the Montreal symposium he had "been deluged with calls from virtually every department of government" for his interpretation of Khachiyan's discovery.

A modest Khachiyan said of himself, "I am a theoretical mathematician, and I'm just working on a class of very difficult mathematical problems."

Ultimately, Khachiyan's findings "were not all that efficient in practice," according to James Renegar, a professor of computer science at Cornell. What his findings did do, "was motivate a lot of other people to follow his work," said Renegar. "His work inspired a tremendous amount of research."

Renegar said when Khachiyan spoke at conferences, attendees took notice and listened. "He was a very independent thinker. He would bring up topics no one was thinking about, almost out of left field. His talks were completely different than anyone else, and everyone would pay attention."

Prior to coming to the United States in 1989, Khachiyan held a series of research and teaching positions at the Moscow Institute of Physics and Technology.

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, according to the university's Office of Media Relations.

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 yesterday at M.J. Murphy Funeral Home, 616 Ridge Road, Monmouth Junction section of South Brunswick.