Nécrologie : L'Homme Mystère

Leonid Khachiyan, mathématicien russe et professeur à l'Université Rutgers qui a publié un théorème révolutionnaire en 1979 qui a contribué à faire avancer le domaine de la programmation linéaire, est décédé le 29 avril à l'âge de 52 ans.

La percée de Khachiyan, appliquant une approche connue sous le nom de méthode ellipsoïde à la programmation linéaire, continue d'aider les informaticiens dans leurs efforts pour relever les défis extrêmement complexes de la planification et de l'allocation des ressources dans des domaines allant de la finance aux télécommunications en passant par l'industrie du transport aérien.

Cette histoire faisait partie de notre numéro de septembre 2005

• Voir le reste du numéro
• S'abonner

Lorsque Khachiyan a publié pour la première fois ses travaux sur la méthode ellipsoïde, il était un mathématicien peu connu de 27 ans étudiant les mathématiques computationnelles au Centre de calcul de l'Académie soviétique des sciences à Moscou. Bien qu'il ait publié ses découvertes dans Doklady Akademii Nauk , le journal très respecté de l'académie, ce n'est que des mois plus tard que deux universitaires basés aux États-Unis ont présenté son article au titre sec – Un algorithme polynomial en programmation linéaire – à un public plus large d'informaticiens et de mathématiciens théoriciens. Après que les résultats ont été rapportés dans La science en 1979, Khachiyan est devenu une célébrité de l'informatique.

Le New-York Fois , qui a décrit les réalisations de Khachiyan dans un article de novembre 1979 intitulé Le mathématicien soviétique n'est plus obscur, l'a appelé l'auteur mystérieux d'un nouveau théorème mathématique qui a secoué le monde de l'analyse informatique. Compte tenu des tensions de l'ère de la guerre froide, le résultat de Khachiyan a suscité à la fois excitation et inquiétude, se souvient Michael Grigoriadis, un collègue de Khachiyan chez Rutgers, qui travaillait pour IBM en 1979. Mais l'importance de sa percée n'a échappé à personne dans le monde universitaire et industriel. Grigoriadis se souvient avoir entendu que le PDG d'IBM avait demandé à ses groupes de recherche d'évaluer la découverte rapportée dans la presse.

La programmation linéaire est une approche mathématique de l'allocation des ressources. Il est apparu dans les années 1940, alors que l'armée américaine luttait pour résoudre des problèmes complexes de planification en temps de guerre. George Dantzig, un étudiant diplômé en mathématiques pendant la Seconde Guerre mondiale qui a été enrôlé par l'US Air Force pour aider à la logistique, a jeté les bases de la programmation linéaire et a introduit sa méthode du simplexe en 1947. L'algorithme du simplexe a fourni une approche pratique pour déterminer comment un un nombre fini de ressources pourrait être alloué de la manière la plus efficace, et il est encore utilisé aujourd'hui.

Un changement majeur par rapport à la pensée dominante de cette époque, la méthode ellipsoïde de Khachiyan a répondu à la question ouverte sur la complexité de la programmation linéaire et a encouragé de nouvelles voies de recherche, a déclaré Grigoriadis. Khachiyan a contribué de manière significative au domaine de l'optimisation combinatoire, dont les applications incluent l'acheminement efficace des paquets de données sur Internet pour réduire le retard global et la gestion des itinéraires de camionnage complexes.

Après avoir obtenu ses diplômes en 1979, Khachiyan a passé la décennie suivante en Russie, occupant une série de postes au Centre de calcul et à l'Institut de physique et de technologie de Moscou. Khachiyan est finalement venu aux États-Unis en 1989 pour un rendez-vous de visite à l'École de recherche opérationnelle et d'ingénierie industrielle de l'Université Cornell. Il s'est ensuite vu proposer un poste au département d'informatique Rutgers, où il a finalement obtenu son poste en 1992. Khachiyan est devenu citoyen américain naturalisé en 2000.

cacher