Leonid Genrikhovich Khachiyan [1] [a] ( / k ɑː tʃ iː ən / ; [4] ruso : Леони́д Ге́нрихович Хачия́н ; 3 de mayo de 1952 - 29 de abril de 2005) fue un matemático e informático soviético y estadounidense .
Fue más famoso por su algoritmo elipsoide (1979) para programación lineal , [5] que fue el primer algoritmo conocido con un tiempo de ejecución polinomial . Aunque se demostró que este algoritmo no era práctico, ha inspirado otros algoritmos aleatorios para programación convexa y se considera un avance teórico significativo.
Khachiyan nació el 3 de mayo de 1952 en Leningrado , hijo de Genrikh Borisovich Khachiyan, matemático y profesor de mecánica teórica , y Zhanna Saakovna Khachiyan, ingeniera civil , de origen armenio . [6] [1] Sus abuelos eran armenios de Karabaj . [7] [8] Tenía dos hermanos: Boris y Yevgeniy (Eugene). [6] [4] Su familia se mudó a Moscú en 1961, cuando tenía nueve años. [1] [6] Recibió una maestría del Instituto de Física y Tecnología de Moscú . [4] En 1978 obtuvo su doctorado en matemáticas computacionales / matemáticas teóricas del Centro de Computación de la Academia Soviética de Ciencias y en 1984 un D.Sc. en informática de la misma institución. [6] [4] [1]
Khachiyan comenzó su carrera en la Academia Soviética de Ciencias, [4] trabajando como investigador en el Centro de Computación de la academia en Moscú. [1] También trabajó como profesor adjunto en el Instituto de Física y Tecnología de Moscú . [9] En 1979 declaró: "Soy un matemático teórico y solo estoy trabajando en una clase de problemas matemáticos muy difíciles". [1] Khachiyan emigró a los Estados Unidos en 1989. [10] [6] Primero enseñó en la Universidad de Cornell como profesor visitante. En 1990 se unió a la Universidad de Rutgers como profesor visitante. [4] [6] [9] Se convirtió en profesor [11] de informática en Rutgers en 1992. [4] [6] En 2005, ocupó el puesto de Profesor II en Rutgers, reservado para aquellos profesores que han alcanzado la eminencia académica en su disciplina. [6]
Khachiyan es más conocido por su artículo de cuatro páginas de febrero de 1979 [12] que indicaba cómo se puede implementar un método elipsoide para programación lineal en tiempo polinomial. [13] [9] El artículo fue traducido a varios idiomas y se difundió por todo el mundo con una rapidez inusual. Los autores de una encuesta de 1981 sobre su trabajo señalaron que "ha causado gran entusiasmo y ha estimulado una avalancha de artículos técnicos" y fue cubierto por los principales periódicos. [13] Originalmente se publicó sin pruebas, que fueron proporcionadas por Khachiyan en un artículo posterior publicado en 1980 [14] y por Peter Gács y Laszlo Lovász en 1981. [15] [9] [13] Fueron Gács y Lovász quienes primero llamaron la atención sobre el artículo de Khachiyan en el Simposio Internacional sobre Programación Matemática en Montreal en agosto de 1979. [13] [6] Se popularizó aún más cuando Gina Kolata lo informó en la revista Science el 2 de noviembre de 1979. [16] [11]
La teoría de Khachiyan se considera innovadora y "ayudó a avanzar en el campo de la programación lineal". [11] Giorgio Ausiello señaló que el método no era práctico, "pero fue un verdadero avance para el mundo de la investigación de operaciones y la informática, ya que demostró que el diseño de algoritmos de tiempo polinomial para la programación lineal era posible y, de hecho, abrió el camino a otros algoritmos más prácticos que se diseñaron en los años siguientes". [17]
Khachiyan hablaba ruso e inglés, pero no armenio . [7] Bahman Kalantari señaló que "para algunos, su acento inglés no siempre era fácil de entender". [18] Un perfil de él publicado en el New York Times en 1979 describió a Khachiyan como "un joven relajado y amigable con un suéter que habla un poco de inglés, que aprendió en la escuela secundaria". [1]
Sus amigos y colegas lo conocían como "Leo" [7] [19] y "Lenya". [20] Václav Chvátal lo describió como "desinteresado, abierto, paciente, simpático, comprensivo, considerado". [19] Michael Todd, otro colega, lo describió como "cínico en política", "muy modesto y amable con sus amigos" e "intolerante a la condescendencia y la pomposidad". [9]
Khachiyan se casó con Olga Pischikova Reynberg, de origen judío-ruso , [21] en 1985. [6] [9] Tuvieron dos hijas, Anna y Nina, [6] [4] que eran adolescentes en el momento de su muerte. [9] Se convirtió en ciudadano estadounidense naturalizado en 2000. [4] [11] Murió de un ataque cardíaco en South Brunswick, Nueva Jersey, el 29 de abril de 2005, a la edad de 52 años . [4] [6] [11]
En 1982 recibió el prestigioso Premio Fulkerson de la Mathematical Programming Society y la American Mathematical Society [10] por sus destacados trabajos en el área de las matemáticas discretas, [6] en particular su artículo de 1979 "Un algoritmo polinomial en programación lineal". [22]
Khachiyan era considerado un "experto destacado en informática cuyo trabajo ayudó a las computadoras a procesar problemas extremadamente complejos". [10] En el momento de su muerte, Haym Hirsh, director del departamento de informática de Rutgers, lo calificó como uno de los científicos informáticos más famosos del mundo. [6] [23] "Los científicos informáticos y los matemáticos dicen que su trabajo ayudó a revolucionar su campo", señaló su obituario en el New York Times . [4] Bahman Kalantari, un amigo y colega de Rutgers, escribió: "Seguramente, Khachiyan siempre seguirá siendo una de las figuras más grandes y legendarias en el campo de la programación matemática". [18]