Loading AI tools
mathématicien canadien De Wikipédia, l'encyclopédie libre
Pour les articles homonymes, voir Edmonds.
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.
| Naissance | |
|---|---|
| Nationalité | |
| Formation | |
| Activités |
| A travaillé pour | |
|---|---|
| Distinction |
Edmonds étudie à l'Université George-Washington où il obtient un bachelor en 1958, et à l'université du Maryland avec un master en 1959[1]. 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'Alan J. Goldman (en). 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.
Ce sont Edmonds et Richard Karp qui ont publié[2] en 1972 l'algorithme de calcul de flot maximum appelé maintenant l'algorithme d'Edmonds-Karp. En 1965, Edmonds publie « Paths, trees, and flowers » [3] 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é « blossom algorithm ». Avec son deuxième article (« Maximum Matching and a Polyhedron with 0-1 Vertices »)[4] 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[5] qui décrit les couplages maximaux[3], appelée la décomposition de Gallai-Edmonds et démontré indépendamment par Tibor Gallai[6],[7]. Il a également travaillé en théorie des matroïdes[8],[9] 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[10]. 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 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[11]. Il est élu fellow dans l'inaugural fellow class de INFORM en 2002. Entre 1970 et 1982, Edmonds a dirigé les thèses de 14 doctorants à l'université de Waterloo[1].
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
