Leonid Khachiyan | |
|---|---|
 | |
| Born | Leonid Genrikhovich Khachiyan (1952-05-03)May 3, 1952 Leningrad, Soviet Union |
| Died | April 29, 2005(2005-04-29) (aged 52) |
| Citizenship | Soviet Union, United States |
| Spouse | |
| Children | 2, includingAnna |
| Awards | Fulkerson Prize (1982) |
| Scientific career | |
| Institutions | Computer Center of the Soviet Academy of Sciences Rutgers University |
Leonid Genrikhovich Khachiyan[1][a] (/kɑːtʃiːən/;[4]Russian:Леони́д Ге́нрихович Хачия́н; May 3, 1952 – April 29, 2005) was a Soviet and American mathematician andcomputer scientist.
He was most famous for hisellipsoid algorithm (1979) forlinear programming,[5] which was the first suchalgorithm known to have apolynomial running time. Even though this algorithm was shown to be impractical, it has inspired otherrandomized algorithms forconvex programming and is considered a significant theoretical breakthrough.
Khachiyan was born on May 3, 1952, inLeningrad toArmenian parents Genrikh Borisovich Khachiyan, a mathematician and professor oftheoretical mechanics, and Zhanna Saakovna Khachiyan, acivil engineer.[6][1] His grandparents wereKarabakh Armenians.[7][8] He had two brothers: Boris and Yevgeniy (Eugene).[6][4] His family moved toMoscow in 1961, when he was nine.[1][6] He received a master's degree from theMoscow Institute of Physics and Technology.[4] In 1978 he earned his Ph.D. incomputational mathematics/theoretical mathematics from theComputer Center of the Soviet Academy of Sciences and in 1984 a D.Sc. incomputer science from the same institution.[6][4][1]
Khachiyan began his career at the Soviet Academy of Sciences,[4] working as a researcher at the academy'sComputer Center in Moscow.[1] He also worked as anadjunct professor at theMoscow Institute of Physics and Technology.[9] In 1979 he stated: "I am a theoretical mathematician and I'm just working on a class of very difficult mathematical problems."[1] Khachiyan immigrated to the United States in 1989.[10][6] He first taught atCornell University as a visiting professor. In 1990 he joinedRutgers University as a visiting professor.[4][6][9] He becameprofessor[11] ofcomputer science at Rutgers in 1992.[4][6] By 2005, he held the position of Professor II at Rutgers, reserved for those faculty who have achieved scholarly eminence in their discipline.[6]
Khachiyan is best known for his four-page February 1979 paper[12] that indicated how anellipsoid method forlinear programming can be implemented in polynomial time.[13][9] The paper was translated into several languages and spread around the world unusually quickly. Authors of a 1981 survey of his work noted that it "has caused great excitement and stimulated a flood of technical papers" and was covered by major newspapers.[13] It was originally published without proofs, which were provided by Khachiyan in a later paper published in 1980[14] and byPeter Gács andLaszlo Lovász in 1981.[15][9][13] It was Gács and Lovász who first brought attention to Khachiyan's paper at the International Symposium on Mathematical Programming in Montreal in August 1979.[13][6] It was further popularized whenGina Kolata reported it inScience Magazine on November 2, 1979.[16][11]
Khachiyan's theory is considered a groundbreaking one that "helped advance the field of linear programming."[11]Giorgio Ausiello noted that the method was not practical, "but it was a real breakthrough for the world of operations research and computer science, since it proved that the design of polynomial time algorithms for linear programming was possible and in fact opened the way to other, more practical, algorithms that were designed in the following years."[17]
Khachiyan spoke Russian and English, but notArmenian.[7] Bahman Kalantari noted that "For some, his English accent wasn’t always easy to understand."[18] A 1979New York Times profile of him described Khachiyan as "a relaxed, friendly young man in a sweater who speaks a little English, which he learned in high school."[1]
He was known as "Leo"[7][19] and "Lenya" to his friends and colleagues.[20]Václav Chvátal described him as "selfless, open, patient, sympathetic, understanding, considerate."[19] Michael Todd, another colleague, described him as "cynical about politics," "very modest and kind to his friends," and "intolerant of condescension and pomposity."[9]
Khachiyan married Olga Pischikova Reynberg, ofRussian-Jewish origin,[21] in 1985.[6][9] They had two daughters,Anna and Nina,[6][4] who were teenagers at the time of his death.[9] He became anaturalized U.S. citizen in 2000.[4][11] He died of aheart attack inSouth Brunswick, New Jersey on April 29, 2005, at the age of 52.[4][6][11]
In 1982 he was awarded the prestigiousFulkerson Prize by theMathematical Programming Society and theAmerican Mathematical Society[10] for outstanding papers in the area of discrete mathematics,[6] particularly his 1979 article "A polynomial algorithm in linear programming."[22]
Khachiyan was considered a "noted expert in computer science whose work helped computers process extremely complex problems."[10] He was called one of the world's most famous computer scientists at the time of his death by Haym Hirsh, chair of the computer science department at Rutgers.[6][23] "Computer scientists and mathematicians say his work helped revolutionize his field," noted hisNew York Times obituary.[4] Bahman Kalantari, a friend and colleague at Rutgers, wrote: "Surely, Khachiyan shall always remain to be among the greatest and most legendary figures in the field of mathematical programming."[18]
| International | |
|---|---|
| Academics | |
