Leonid Khachiyan

Leonid Genrikhovich Khachiyan (ruso: Леони́д Ге́нрихович Хачия́н; 3 de mayo de 1952 -29 de abril de 2005) fue un matemático e informático soviético y estadounidense. científico.

Fue más famoso por su algoritmo elipsoide (1979) para programación lineal, que fue el primer algoritmo de este tipo conocido que tenía un tiempo de ejecución polinomial. Aunque se demostró que este algoritmo no era práctico, ha inspirado otros algoritmos aleatorios para la programación convexa y se considera un avance teórico significativo.

Vida temprana y educación

Khachiyan nació el 3 de mayo de 1952 en Leningrado, de padres armenios Genrikh Borisovich Khachiyan, matemático y profesor de mecánica teórica, y Zhanna Saakovna Khachiyan, ingeniera civil. Sus abuelos eran armenios de Karabaj. Tenía dos hermanos: Boris y Yevgeniy (Eugene). Su familia se mudó a Moscú en 1961, cuando él tenía nueve años. Recibió una maestría del Instituto de Física y Tecnología de Moscú. En 1978 obtuvo su doctorado. en matemáticas computacionales/matemáticas teóricas del Centro de Computación de la Academia de Ciencias Soviética y en 1984 un D.Sc. en informática de la misma institución.

Carrera

Khachiyan comenzó su carrera en la Academia Soviética de Ciencias, trabajando como investigador en el Centro de Computación de la academia en Moscú. También trabajó como profesor adjunto en el Instituto de Física y Tecnología de Moscú. En 1979 afirmó: "Soy un matemático teórico y sólo estoy trabajando en una clase de problemas matemáticos muy difíciles". Khachiyan emigró a los Estados Unidos en 1989. Primero enseñó en la Universidad de Cornell como profesor visitante. En 1990 se incorporó a la Universidad de Rutgers como profesor invitado. Se convirtió en profesor de informática en Rutgers en 1992. En 2005, ocupaba el puesto de Profesor II en Rutgers, reservado para aquellos profesores que habían alcanzado una eminencia académica en su disciplina.

Trabajar en programación lineal

Método del elipsoide

Khachiyan es mejor conocido por su artículo de cuatro páginas de febrero de 1979 que indicaba cómo se puede implementar un método elipsoide para programación lineal en tiempo polinomial. El artículo fue traducido a varios idiomas y se difundió por todo el mundo con una rapidez inusual. Los autores de un estudio realizado en 1981 sobre su trabajo señalaron que "ha causado gran entusiasmo y estimulado una avalancha de artículos técnicos" en la actualidad. y fue cubierto por los principales periódicos. Se publicó originalmente sin pruebas, que fueron proporcionadas por Khachiyan en un artículo posterior publicado en 1980 y por Peter Gács y Laszlo Lovász en 1981. Fueron Gács y Lovász quienes llamaron la atención por primera vez sobre el artículo de Khachiyan en el Simposio Internacional sobre Programación Matemática en Montreal en agosto de 1979. Se popularizó aún más cuando Gina Kolata lo informó en la Revista Science el 2 de noviembre de 1979.

La teoría de Khachiyan se considera innovadora y "ayudó a avanzar en el campo de la programación lineal". Giorgio Ausiello señaló que el método no era práctico, "pero fue un verdadero avance para el mundo de la investigación operativa 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". paso a otros algoritmos más prácticos que se diseñaron en los años siguientes."

Vida y muerte personal

Khachiyan hablaba ruso e inglés, pero no armenio. Bahman Kalantari señaló que "para algunos, su acento inglés no siempre fue fácil de entender". Un perfil suyo de 1979 del New York Times describía 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".

Era conocido como "Leo" y "Lenya" a sus amigos y colegas. Václav Chvátal lo describió como "desinteresado, abierto, paciente, comprensivo, comprensivo y considerado". Michael Todd, otro colega, lo describió como "cínico en política", dijo. "muy modesto y amable con sus amigos" e "intolerante a la condescendencia y la pomposidad"

Khachiyan se casó con Olga Pischikova Reynberg, de origen judío ruso, en 1985. Tuvieron dos hijas, Anna y Nina, que eran adolescentes en el momento de su muerte. Se naturalizó ciudadano estadounidense en 2000. Murió de un ataque cardíaco en South Brunswick, Nueva Jersey, el 29 de abril de 2005, a la edad de 52 años.

Reconocimiento

En 1982 recibió el prestigioso Premio Fulkerson de la Sociedad de Programación Matemática y la Sociedad Estadounidense de Matemáticas por sus trabajos destacados en el área de las matemáticas discretas, en particular su artículo de 1979 "Un algoritmo polinomial en programación lineal".;

Khachiyan era considerado un "destacado experto en informática cuyo trabajo ayudó a las computadoras a procesar problemas extremadamente complejos". Haym Hirsh, presidente del departamento de informática de Rutgers, lo llamó uno de los científicos informáticos más famosos del mundo en el momento de su muerte. "Los informáticos y matemáticos dicen que su trabajo ayudó a revolucionar su campo". señaló su obituario del New York Times. Bahman Kalantari, amigo y colega de Rutgers, escribió: "Seguramente, Khachiyan siempre estará entre las figuras más grandes y legendarias en el campo de la programación matemática".