Martin 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) |
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.
Parcours professionnel modifier
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 modifier
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 modifier
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 modifier
- (en) Martin Dyer et Catherine Greenhill, « Corrigendum: The complexity of counting graph homomorphisms », Random Structures and Algorithms, Wiley-Blackwell, vol. 25, no 3, , p. 346-352 (ISSN 1042-9832 et 1098-2418, DOI 10.1002/RSA.20036)
- (en) Martin Dyer, Alan Frieze et Ravi Kannan, « A random polynomial-time algorithm for approximating the volume of convex bodies », Journal of the ACM, New York, ACM, vol. 38, no 1, , p. 1-17 (ISSN 0004-5411 et 1557-735X, OCLC 783892264 et 1514518, DOI 10.1145/102782.102783)
Notes et références modifier
- (en) « Martin E. Dyer », sur le site du Mathematics Genealogy Project
- Laudatio pour le prix de l'EATCS.
- 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)
- 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)
- Prix Fulkerson 1991
Liens externes modifier
- Ressources relatives à la recherche :
