- Leonid Khachiyan
-
Leonid Khachiyan Nacimiento 3 de mayo, 1952
San Petersburgo, RusiaFallecimiento 29 de abril, 2005
Nueva Jersey, Estados UnidosResidencia Rusia y Estados Unidos Nacionalidad 
RusaCampo Programación lineal
Complejidad computacionalInstituciones Universidad Rutgers Alma máter Academia de las Ciencias de Rusia Conocido por Algoritmo del elipsoide Premios
destacadosPremio Fulkerson Leonid Khachiyan (armenio: Լեոնիդ Գենրիխովիչ Խաչիյան; ruso: Леонид Генрихович Хачиян; n. San Petersburgo, Rusia en 3 de mayo, 1952 – † Nueva Jersey, Estados Unidos en 29 de abril, 2005) fue un connotado matemático ruso de origen armenio, catedrático de ciencias de la computación de la Universidad Rutgers, principalmente conocido por su demostración de la polinomialidad de la programación lineal.[1]
Contenido
Biografía
Khachiyan nació en San Petersburgo y se trasladó a Moscú con su familia a los 9 años de edad. Allí estudió en el Centro de Computación de la Academia rusa de las Ciencias, donde obtuvo un doctorado en matemática computacional en 1978 y se convirtió en Doctor en Ciencias de la Computación en 1984. En 1982 ganó el prestigioso Premio Fulkerson de la Sociedad de Programación Matemática y la Sociedad Americana de Matemática, por sus artículos en el área de matemática discreta.
Antes de llegar a Estados Unidos en 1989, Khachiyan participó en docencia y una serie de investigaciones en el Centro de Computación de la Academia rusa de las Ciencias y en el Instituto de Moscú de Ciencia y Tecnología. En 1989 llega a la Escuela de Investigación Operacional e Ingeniería Industrial de la Universidad de Cornell, como profesor visitante, instalándose en 1990 finalmente en la Universidad Rutgers.
Después de instalarse en Estados Unidos, Khachiyan comenzó a trabajar en nuevos temas de investigación, pero también retomó algunos de sus temas preferidos en Rusia, como el de la complejidad de determinar el volumen máximo de un elipsoide, y el redondeo de politopos. Escribió una serie de artículos con Bahman Kalantari sobre diversos escalamientos de matrices y sobre balances de carga. Además hizo importantes aportes en lógica computacional.
Khachiyan falleció de un ataque al corazón, según dijeron sus familiares.[2]
El algoritmo del elipsoide
En 1979, a los 25 años de edad, Leonid Khachiyan demostró, mediante un inusual método que llamó Algoritmo del elipsoide, que la programación lineal podía ser computada siempre en tiempo polinomial.[1] Su artículo causó tanto revuelo en Estados Unidos, incluso siendo citado en el The New York Times, donde fue relacionado erróneamente con el Programa Sputnik de los rusos, que en Rusia tuvo que atestiguar ante el Government Committee for Science and Technology (el equivalente ruso de la National Science Foundation estadounidense) que nada tenía que ver su descubrimiento con la carrera espacial.[3]
Dado que la revista científica donde publicó su artículo restringe el número de páginas a un máximo de cuatro, Khachiyan republicó su idea original en un nuevo artículo el año siguiente,[4] incluyendo las demostraciones previamente omitidas.[3]
Aunque este algoritmo actualmente se considera poco práctico, por el alto grado polinómico de su complejidad computacional, significó un descubrimiento sumamente importante en el área, y un punto de partida para el desarrollo de algoritmos más sofisticados y eficientes.
Referencias
- ↑ a b Khachiyan, L. (1979), A polynomial algorithm in linear programming, 20, Soviet Math. Doklady, pp. 191-194
- ↑ Obituario del The New York Times
- ↑ a b Boros, E.; Gurvich, V. (2008), Scientific contributions of Leo Khachiyan (a short overview), 156, Discrete Applied Mathematics, pp. 2232-2240
- ↑ Kachiyan, L. (1980), Polynomial algorithms for linear programming, 20, USSR Comput. Math. Math. Phys., pp. 51–68
Enlaces externos
Categorías:- Nacidos en 1952
- Fallecidos en 2005
- Matemáticos de Rusia
- Informáticos teóricos de Rusia
- Alumnado del Instituto de Física y Tecnología de Moscú
- Profesores del Instituto de Física y Tecnología de Moscú
Wikimedia foundation. 2010.
