Jump to content

Leonid Khachiyan

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by Bmf 051 (talk | contribs) at 18:05, 27 July 2020 (Reverted 1 edit by 42.201.241.75 (talk) to last revision by 2603:9000:8307:2000:BD22:3D53:A462:233B (TW)). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

Leonid Khachiyan
Born(1952-05-03)May 3, 1952
Leningrad, Russian SFSR, Soviet Union
DiedApril 29, 2005(2005-04-29) (aged 52)
South Brunswick, New Jersey, U.S.
NationalityArmenian
CitizenshipSoviet Union, United States
AwardsFulkerson Prize (1982)
Scientific career
InstitutionsComputer 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 and computer scientist.

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

Early life and education

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 grandfather was a Karabakh Armenian.[7] 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

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.[8] 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.[9][6] He first taught at Cornell University as a visiting professor. In 1990 he joined Rutgers University as a visiting professor.[4][6][8] He became professor[10] of computer science at Rutgers in 1992.[4][6] By 2005, he held the position of Professor II at Rutgers.[6]

Work on linear programming

Ellipsoid method

Khachiyan is best known for his four-page February 1979 paper[11] that indicated how an ellipsoid method for linear programming can be implemented in polynomial time.[12][8] The paper was translated into several languages and spread around the world unusually fast. 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.[12] It was originally published without proofs, which were provided by Khachiyan in a later paper published in 1980[13] and by Peter Gács and Laszlo Lovász in 1981.[14][8][12] It were 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.[12][6] It was further popularized when Gina Kolata reported it in Science Magazine on November 2, 1979.[15][10]

Khachiyan's theory is considered a groundbreaking one that "helped advance the field of linear programming."[10] 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."[16]

Personal life and death

Khachiyan spoke Russian and English, but not Armenian.[7] Bahman Kalantari noted that "For some, his English accent wasn’t always easy to understand."[17] The 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][18] and "Lenya" to his friends and colleagues.[19] Václav Chvátal described him as "selfless, open, patient, sympathetic, understanding, considerate."[18] Michael Todd, another colleague, described him as "cynical about politics,"[20] "very modest and kind to his friends," and "intolerant of condescension and pomposity."[8]

Khachiyan married Olga Pischikova Reynberg in 1985.[6][8] They had two daughters, Anna and Nina,[6][4] who were teenagers at the time of his death.[8] He became a naturalized U.S. citizen in 2000.[4][10] He died of a heart attack in South Brunswick, New Jersey on April 29, 2005, at the age of 52.[4][6][10]

Recognition

In 1982 he was awarded the prestigious Fulkerson Prize by the Mathematical Programming Society and the American Mathematical Society[9] for outstanding papers in the area of discrete mathematics,[6] particularly his 1979 article "A polynomial algorithm in linear programming."[21]

Khachiyan was considered a "noted expert in computer science whose work helped computers process extremely complex problems."[9] 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][22] "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."[17]

References

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.
  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. May 3, 2005. (archived PDF), (alternative archived version)
  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. ^ 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.
  9. ^ a b c "Leonid Khachiyan, 52; Computer Science Expert at Rutgers". Los Angeles Times. May 5, 2005.
  10. ^ a b c d e Madden, Andrew P. (September 1, 2005). "Obituary: Mystery Man". MIT Technology Review. Massachusetts Institute of Technology. (archived PDF)
  11. ^ 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).
  12. ^ 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.
  13. ^ 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.
  14. ^ 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.
  15. ^ 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.
  16. ^ 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.
  17. ^ a b Kalantari, Bahman (2005). "My Memories of Leonid Khachiyan and a Personal Tribute for His Contributions in Linear Programming" (PDF). Semantic Scholar. Allen Institute for AI.
  18. ^ 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.
  19. ^ "Leonid Khachiyan, 1952-2005: An Appreciation". SIAM News. Society for Industrial and Applied Mathematics. December 1, 2005. (cached)
  20. ^ Malwitz, Rick (4 May 2005). "Leonid Khachiyan: Rutgers computer scientist dies". Home News Tribune.
  21. ^ "The Fulkerson Prize". mathopt.org. Mathematical Optimization Society. Archived from the original on 12 February 2019.
  22. ^ "Leonid Khachiyan, professor, leading computer scientist". The Boston Globe. (via Associated Press). May 5, 2005. Archived from the original on 4 September 2017.



Flag of ArmeniaScientist icon Stub icon

This article about an Armenian scientist is a stub. You can help Wikipedia by expanding it.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Leonid_Khachiyan&oldid=969839511"