Martin Dyer

Martin Edward Dyer (né le à Ryde, sur l'Île de Wight, en Angleterre) est un mathématicien et un information théoricien, spécialiste de la complexité des problèmes d'optimisation. Il est professeur à la School of Computing de l'université de Leeds, en Angleterre.

Martin Edward Dyer
Naissance
Ryde
Domaines mathématiques, informatique théorique, complexité des problèmes d'optimisation
Institutions professeur à la School of Computing de l'université de Leeds
Diplôme Ph. D. à l'université de Leeds
Formation université de Leeds, Imperial College London
Directeur de thèse Les G. Proll
Renommé pour algorithme linéaire pour des programmes linéaires, algorithme randomisé polynomial d'approximation du volume d'un objet convexe
Distinctions Prix Fulkerson (1991), Prix EATCS (2013)

Parcours professionnel

Il obtient un diplôme de gradué à l'université de Leeds en 1967, un M.S. à l'Imperial College London en 1968 et un Ph. D. à l'université de Leeds in 1979 (« Vertex Enumeration in Mathematical Programming - Methods and Applications ».) sous la direction de Les G. Proll[1].

Recherche

Ses domaines de recherche sont l'informatique théorique, l'optimisation discrète et la combinatoire. Il travaille notamment sur la complexité du dénombrement et sur l'efficacité des algorithmes de dénombrement approché à l'aide de chaînes de Markov. Les contributions principales sont les suivantes[2] :

  • Martin Dyer et indépendamment Nimrod Megiddo, découvrent des algorithmes linéaires en temps pour des programmes linéaires en basse dimension. Ces algorithmes sont améliorés ensuite par Dyer, Megiddo et d'autres et conduisent à des algorithmes très efficaces en temps linéaire qui ont des applications importantes en géométrie algorithmique.
  • En analyse probabiliste d'algorithmes, les résultats de Dyer et Frieze montrent que de nombreux problèmes NP-difficiles en optimisation combinatoire peuvent être résolu en temps polynomial en moyenne si les instances sont tirées selon des distributions naturelles.
  • Un article, avec Alan Frieze et Ravindran Kannan[3] décrit un algorithme randomisé en temps polynomial d'approximation du volume d'un objet convexe en grande dimension. Cet article est le plus connu. Les approches usuelles ont un temps d'exécution qui croît exponentiellement avec le nombre de dimensions. L'article des trois auteurs décrit le premier algorithme polynomial en fonction de la dimension.
  • Application de la méthode de couplage de chemins pour démontrer que des chaînes de Markov sont rapidement mélangeantes (avec Russ Bubley)[4]
  • Étude de la complexité du dénombrement de problèmes de satisfaction de contraintes.

Prix et distinctions

En 1991, Martin Dyer reçoit, avec Alan Frieze and Ravi Kannan, le Prix Fulkerson[5] en mathématiques discrètes pour leur article du journal de l'ACM[3]. En 2013, l'EATCS lui attribue le Prix EATCS. Il reçoit le prix Gödel en 2021.

Publications

Notes et références
  1. (en) « Martin E. Dyer », sur le site du Mathematics Genealogy Project
  2. Laudatio pour le prix de l'EATCS.
  3. Martin Dyer, Alan Frieze et Ravindran Kannan, « A random polynomial-time algorithm for approximating the volume of convex bodies », Journal of the ACM, vol. 38, no 1,‎ , p. 1–17 (DOI 10.1145/102782.102783, lire en ligne)
  4. Russ Bubley et Martin Dyer, « Path coupling: a technique for proving rapid mixing in Markov chains », Proceedings of the 38th Annual Symposium on Foundations of Computer Science, IEEE,‎ , p. 223–231 (DOI 10.1109/SFCS.1997.646111, lire en ligne)
  5. Prix Fulkerson 1991
(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Martin Dyer » (voir la liste des auteurs).

Liens externes
  • Portail des mathématiques
  • Portail de l'informatique théorique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.