Obituario: Mystery Man

Leonid Khachiyan, un matemático ruso y profesor de la Universidad de Rutgers que publicó un teorema pionero en 1979 que ayudó a avanzar en el campo de la programación lineal, murió el 29 de abril a la edad de 52 años.

El avance de Khachiyan, que aplica un enfoque conocido como método elipsoide a la programación lineal, continúa ayudando a los informáticos en sus esfuerzos por abordar los desafíos enormemente complejos de la programación y la asignación de recursos en campos que van desde las finanzas hasta las telecomunicaciones y la industria de las aerolíneas.

Esta historia fue parte de nuestro número de septiembre de 2005

• Ver el resto del número
• Suscribir

Cuando Khachiyan publicó por primera vez su trabajo sobre el método elipsoide, era un matemático poco conocido de 27 años que estudiaba matemáticas computacionales en el Centro de Computación de la Academia de Ciencias Soviética en Moscú. Aunque publicó sus hallazgos en Doklady Akademii Nauk , la revista muy respetada de la academia, no fue sino hasta meses después que dos académicos con sede en los EE. UU. presentaron su artículo titulado secamente, A Polynomial Algorithm in Linear Programming, a una audiencia más amplia de científicos informáticos y matemáticos teóricos. Después de que se informaron los hallazgos en Ciencias en 1979, Khachiyan se convirtió en una celebridad de la informática.

La nueva york Veces , que describió el logro de Khachiyan en un artículo de noviembre de 1979 titulado El matemático soviético ya no es más oscuro, lo llamó el autor misterioso de un nuevo teorema matemático que ha sacudido el mundo del análisis informático. Dadas las tensiones de la era de la Guerra Fría, el resultado de Khachiyan provocó tanto entusiasmo como alarma, recuerda Michael Grigoriadis, un colega de Khachiyan en Rutgers, que trabajaba para IBM en 1979. Pero la importancia de su avance no se le escapó a nadie en la academia y la industria. Grigoriadis recuerda haber oído que el director ejecutivo de IBM pidió a sus grupos de investigación que evaluaran el descubrimiento informado en la prensa.

La programación lineal es un enfoque matemático para la asignación de recursos. Surgió en la década de 1940, cuando el ejército estadounidense luchaba por abordar cuestiones complejas de planificación en tiempos de guerra. George Dantzig, un estudiante graduado en matemáticas durante la Segunda Guerra Mundial que fue reclutado por la Fuerza Aérea de los Estados Unidos para ayudar con la logística, sentó las bases para la programación lineal e introdujo su método simplex en 1947. El algoritmo simplex proporcionó un enfoque práctico para determinar cómo un Se podría asignar un número finito de recursos de la manera más eficiente, y todavía se usa en la actualidad.

Una desviación importante del pensamiento predominante en esa época, el método elipsoide de Khachiyan respondió la pregunta abierta sobre la complejidad de la programación lineal y alentó nuevas vías de investigación, dijo Grigoriadis. Khachiyan contribuyó significativamente al campo de la optimización combinatoria, cuyas aplicaciones incluyen el enrutamiento eficiente de paquetes de datos a través de Internet para reducir el retraso general y la gestión de rutas complejas de camiones.

Después de establecer sus credenciales académicas en 1979, Khachiyan pasó la siguiente década en Rusia, ocupando una serie de puestos en el Centro de Computación y en el Instituto de Física y Tecnología de Moscú. Khachiyan finalmente llegó a los Estados Unidos en 1989 para una cita de visita en la Escuela de Investigación de Operaciones e Ingeniería Industrial de la Universidad de Cornell. Luego le ofrecieron un puesto en el Departamento de Ciencias de la Computación de Rutgers, donde finalmente obtuvo la titularidad en 1992. Khachiyan se convirtió en ciudadano estadounidense naturalizado en 2000.

esconder