Jack R. Edmonds, né le , est un mathématicien et informaticien théoricien canadien, considéré comme l'un des contributeurs les plus importants dans le domaine de l'optimisation combinatoire.
Biographie Edmonds étudie à l'Université George-Washington où il obtient un bachelor en 1958, et à l'université du Maryland avec un master en 1959.. Il travaille ensuite jusqu'en 1969 dans le département de recherche opérationnelle au National Institute of Standards and Technology sous la direction d'. En 1969, il est nommé professeur au département d'optimisation combinatoire de la faculté de mathématiques de l'Université de Waterloo, où il enseigne jusqu'à sa retraite en 1999, à l'exception de la période entre 1991 et 1993.
Contributions
Ce sont Edmonds et Richard Karp qui ont publié. en 1972 l'algorithme de calcul de flot maximum appelé maintenant l'algorithme d'Edmonds-Karp. En 1965, Edmonds publie « Paths, trees, and flowers » . qui est le premier algorithme en temps polynomial pour le problème du couplage en théorie des graphes : l'algorithme d'Edmonds pour les couplages, aussi appelé . Avec son deuxième article (« Maximum Matching and a Polyhedron with 0-1 Vertices »). sur ce thème, il jette les bases de l'interaction entre la géométrie des polyèdre et l'optimisation combinatoire pour aboutir à la construction d’algorithmes efficaces.
Il est aussi connu pour un théorème de structure. qui décrit les couplages maximaux, appelée la décomposition de Gallai-Edmonds et démontré indépendamment par Tibor Gallai... Il a également travaillé en théorie des matroïdes.« Sa théorie des partitions et intersections de matroîdes reste un des résultats les plus profonds de ce domaine. » (Laudatio du prix de théorie John von Neumann). qui, montre que le problème de l’intersection des matroïdes est à la fois dans NP et co-NP.
Avec Ellis L. Johnson, Edmonds résout le problème du postier chinois avec des méthodes de couplage.. Ils montrent que le problème peut être résolu en temps polynomial, contrairement problème du voyageur de commerce qui lui ressemble mais qui est beaucoup plus difficile).
Edmonds a également travaillé sur le branchement optimal ; l'algorithme dit d'Edmonds ou de Chu–Liu est un algorithm pour trouver une arborescence couvrante de poids minimal (appelée branchement optimal) ; c'est l'analogue de l'arbre couvrant de poids minimal. L'algorithme a été proposé indépendamment d'abord par Yoeng-Jin Chu et Tseng-Hong Liu (en 1965) puis par Jack Edmonds (en 1967).
Edmonds a été lauréat du prix de théorie John von Neumann en 1985.. Il est élu fellow dans linaugural fellow class de INFORM en 2002. Entre 1970 et 1982, Edmonds a dirigé les thèses de 14 doctorants à l'université de Waterloo.
Bibliographie . Publications (sélection)
.
Notes et références
Liens externes
Biography de Jack Edmonds sur lInstitute for Operations Research and the Management Sciences. Publications de Jack Edmonds sur DBLP .
Catégorie:Informaticien canadien Catégorie:Personnalité en combinatoire Catégorie:Mathématicien canadien du XXe siècle Catégorie:Optimisation combinatoire Catégorie:Personnalité en informatique théorique Catégorie:Professeur à l'Université de Waterloo Catégorie:Universitaire canadien Catégorie:Recherche opérationnelle Catégorie:Lauréat du prix de théorie John-von-Neumann Catégorie:Naissance en avril 1934