Leonid Khachiyan

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda
Leonid Khachiyan
Nacimiento 3 de mayo, 1952
San Petersburgo, Rusia
Fallecimiento 29 de abril, 2005
Nueva Jersey, Estados Unidos
Residencia Rusia y Estados Unidos
Nacionalidad Bandera de Rusia Rusa
Campo Programación lineal
Complejidad computacional
Instituciones Universidad Rutgers
Alma máter Academia de las Ciencias de Rusia
Conocido por Algoritmo del elipsoide
Premios
destacados
Premio 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]

Biografía[editar]

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[editar]

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[editar]

  1. a b Khachiyan, L. (1979), A polynomial algorithm in linear programming, 20, Soviet Math. Doklady, pp. 191-194 
  2. Obituario del The New York Times
  3. a b Boros, E.; Gurvich, V. (2008), Scientific contributions of Leo Khachiyan (a short overview), 156, Discrete Applied Mathematics, pp. 2232-2240 
  4. Kachiyan, L. (1980), Polynomial algorithms for linear programming, 20, USSR Comput. Math. Math. Phys., pp. 51–68 

Enlaces externos[editar]