Wikipedia

Leonid Khachiyan

Leonid Genrikhovich Khachiyan[1][a] (/kɑːtʃiːən/;[4] Russian: Леони́д Ге́нрихович Хачия́н; May 3, 1952 – April 29, 2005) was a Soviet and American mathematician and computer scientist.

Leonid Khachiyan
Born
Leonid Genrikhovich Khachiyan

(1952-05-03)May 3, 1952
Leningrad, Soviet Union
DiedApril 29, 2005(2005-04-29) (aged 52)
South Brunswick, New Jersey, U.S.
CitizenshipSoviet Union, United States
Spouse
Olga Pischikova Reynberg
​
​
(m. 1985)​
Children2, including Anna
AwardsFulkerson Prize (1982)
Scientific career
InstitutionsComputer Center of the Soviet Academy of Sciences
Rutgers University

He was most famous for his ellipsoid algorithm (1979) for linear programming,[5] which was the first such algorithm known to have a polynomial running time. Even though this algorithm was shown to be impractical, it has inspired other randomized algorithms for convex programming and is considered a significant theoretical breakthrough.

Early life and education

edit

Khachiyan was born on May 3, 1952, in Leningrad to Armenian parents Genrikh Borisovich Khachiyan, a mathematician and professor of theoretical mechanics, and Zhanna Saakovna Khachiyan, a civil engineer.[6][1] His grandparents were Karabakh Armenians.[7][8] He had two brothers: Boris and Yevgeniy (Eugene).[6][4] His family moved to Moscow in 1961, when he was nine.[1][6] He received a master's degree from the Moscow Institute of Physics and Technology.[4] In 1978 he earned his Ph.D. in computational mathematics/theoretical mathematics from the Computer Center of the Soviet Academy of Sciences and in 1984 a D.Sc. in computer science from the same institution.[6][4][1]

Career

edit

Khachiyan began his career at the Soviet Academy of Sciences,[4] working as a researcher at the academy's Computer Center in Moscow.[1] He also worked as an adjunct professor at the Moscow 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 at Cornell University as a visiting professor. In 1990 he joined Rutgers University as a visiting professor.[4][6][9] He became professor[11] of computer 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]

Work on linear programming

edit

Ellipsoid method

edit

Khachiyan is best known for his four-page February 1979 paper[12] that indicated how an ellipsoid method for linear 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 by Peter Gács and Laszlo 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 when Gina Kolata reported it in Science 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]

Personal life and death

edit

Khachiyan spoke Russian and English, but not Armenian.[7] Bahman Kalantari noted that "For some, his English accent wasn’t always easy to understand."[18] A 1979 New 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, of Russian-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 a naturalized U.S. citizen in 2000.[4][11] He died of a heart attack in South Brunswick, New Jersey on April 29, 2005, at the age of 52.[4][6][11]

Recognition

edit

In 1982 he was awarded the prestigious Fulkerson Prize by the Mathematical Programming Society and the American 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 his New 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]

References

edit
Notes
  1. ^ His last name was often spelled in English as Khachian.[2][3] Anglicized as Leonid Henry Khachiyan.[4]
Citations
  1. ^ a b c d e f g Whitney, Craig R. (November 27, 1979). "Soviet Mathematician Is Obscure No More". The New York Times.
  2. ^ Boas, Harold P. (30 November 1979). "Linear Programming Discovery". Science. 206 (4422): 1022. Bibcode:1979Sci...206.1022B. doi:10.1126/science.206.4422.1022-c.
  3. ^ Browne, Malcolm W. (November 7, 1979). "A Soviet Discovery Rocks World of Mathematics". The New York Times.
  4. ^ a b c d e f g h i j k l Pearce, Jeremy (May 22, 2005). "Leonid Khachiyan Is Dead at 52; Advanced Computer Math". The New York Times.
  5. ^ Lawler, Eugene L. (1980). "The Great Mathematical Sputnik of 1979". The Sciences. 20 (7): 12–15. doi:10.1002/j.2326-1951.1980.tb01345.x. S2CID 56588045.
  6. ^ a b c d e f g h i j k l m n "World Renowned Computer Scientist Leonid G. Khachiyan Dies at 52". Rutgers University Department of Computer Science. Archived from the original on 2016-09-11. (archived PDF)
  7. ^ a b c Gurvich, Vladimir (6 June 2008). "Recalling Leo". Discrete Applied Mathematics. 156 (11): 1957–1960. doi:10.1016/j.dam.2008.04.013.
  8. ^ Khachiyan, Anna (April 25, 2020). "Family portrait of Armenian ancestors, Nagorno-Karabakh, 1920s (great great grandparents in the center, grandmother little girl on the left with the pigtails)". Twitter. Archived from the original on 17 August 2020. Retrieved 17 August 2020.
  9. ^ a b c d e f g Todd, Michael (October 2005). "Leonid Khachiyan, 1952–2005: An Appreciation". SIAG/OPT Views-and-News. 16 (1–2). SIAM Activity Group on Optimization: 4–6. CiteSeerX 10.1.1.131.3938.
  10. ^ a b c "Leonid Khachiyan, 52; Computer Science Expert at Rutgers". Los Angeles Times. May 5, 2005.
  11. ^ a b c d e Madden, Andrew P. (September 1, 2005). "Obituary: Mystery Man". MIT Technology Review. Massachusetts Institute of Technology. (archived PDF)
  12. ^ Khachiyan, L. G. 1979. "A Polynomial Algorithm in Linear Programming". Doklady Akademii Nauk SSSR 244, 1093-1096 (translated in Soviet Mathematics Doklady 20, 191-194, 1979).
  13. ^ a b c d Bland, Robert G.; Goldfarb, Donald; Todd, Michael J. (1981). "The Ellipsoid Method: A Survey" (PDF). Operations Research. 29 (6): 1039–1091. doi:10.1287/opre.29.6.1039. JSTOR 170362. Archived from the original (PDF) on 2015-07-01.
  14. ^ Khachiyan, L. G. 1980. "Polynomial Algorithms in Linear Programming". Zhurnal Vychisditel'noi Matematiki i Matematicheskoi Fiziki (USSR Computational Mathematics and Mathematical Physics) 20, 51-68.
  15. ^ Gács, Peter; Lovász, Laszlo (1981). "Khachiyan's algorithm for linear programming". In König, H.; Korte, B.; Ritter, K. (eds.). Mathematical Programming at Oberwolfach. Mathematical Programming Studies. Vol. 14. pp. 61–68. doi:10.1007/BFb0120921. ISBN 978-3-642-00805-4.
  16. ^ Kolata, Gina Bari (November 2, 1979). "Mathematicians Amazed by Russian's Discovery". Science. 206 (4418): 545–546. Bibcode:1979Sci...206..545B. doi:10.1126/science.206.4418.545. JSTOR 1749236. PMID 17759415.
  17. ^ Ausiello, Giorgio (2018). The Making of a New Science: A Personal Journey Through the Early Years of Theoretical Computer Science. Springer. p. 174. ISBN 9783319626802.
  18. ^ a b Kalantari, Bahman (2005). "My Memories of Leonid Khachiyan and a Personal Tribute for His Contributions in Linear Programming" (PDF). Allen Institute for AI. S2CID 15568389. Archived from the original (PDF) on 2020-01-13.
  19. ^ a b Chvátal, Václav (6 June 2008). "Remembering Leo Khachiyan". Discrete Applied Mathematics. 156 (11): 1961–1962. doi:10.1016/j.dam.2007.08.001.
  20. ^ Todd, Michael J. (1 December 2005). "SIAM: Leonid Khachiyan, 1952 - 2005: An Appreciation". archive.siam.org. Philadelphia: Society for Industrial and Applied Mathematics. Archived from the original on 21 January 2021. Retrieved 27 June 2021.
  21. ^ Khachiyan, Anna (December 4, 2019). "I had such a shambolic, dysfunctional upbringing my parents didn't even bother to teach me chess — unheard of and frankly shameful for Russian family of Armenian and Ashkenazi origins lol!". Twitter. Archived from the original on 17 August 2020. Retrieved 17 August 2020.
  22. ^ "The Fulkerson Prize". mathopt.org. Mathematical Optimization Society. Archived from the original on 12 February 2019.
  23. ^ "Leonid Khachiyan, professor, leading computer scientist". The Boston Globe. (via Associated Press). May 5, 2005. Archived from the original on 4 September 2017.
edit


Retrieved from "https://en.wiki.x.io/w/index.php?title=Leonid_Khachiyan&oldid=1254690738"