Martin dyer
Martin Edward Dyer
Martin Edward Dyer (født den16. juli 1946i Ryde , på Isle of Wight , England ) er en matematiker og informasjonsteoretiker som spesialiserer seg på kompleksiteten i optimaliseringsproblemer. Han er professor ved School of Computing ved University of Leeds , England.
Profesjonell karriere
Han fikk et diplom utdannet til University of Leeds i 1967, en MS i Imperial College London i 1968 og en Ph D.. Ved University of Leeds i 1979 ( "Vertex Enumeration i Mathematical Programming -. Methods and Applications» ) Edited av Les G. Proll.
Undersøkelser
Hans forskningsfelt er teoretisk informatikk , diskret optimalisering og kombinatorikk . Han arbeider spesielt med kompleksiteten i oppregningen og på effektiviteten av tilnærmede oppregningsalgoritmer ved bruk av Markov-kjeder. Hovedbidragene er som følger:
- Martin Dyer og uavhengig Nimrod Megiddo, oppdager lineære algoritmer i tide for lineære programmer i lav dimensjon. Disse algoritmene forbedres deretter av Dyer, Megiddo og andre og fører til svært effektive algoritmer på lineær tid som har viktige applikasjoner i beregningsgeometri .
- I sannsynlighetsanalyse av algoritmer viser resultatene av Dyer og Frieze at mange NP-vanskelige problemer i kombinatorisk optimalisering i gjennomsnitt kan løses i polynomtid hvis forekomster er tegnet i henhold til naturlige fordelinger.
- En artikkel med Alan Frieze og Ravindran Kannan beskriver en randomisert algoritme i polynomisk tid for tilnærming til volumet til et konveks objekt i stor dimensjon. Denne artikkelen er den mest kjente. De vanlige tilnærmingene har en utførelsestid som øker eksponentielt med antall dimensjoner. Artikkelen til de tre forfatterne beskriver den første polynomalgoritmen i henhold til dimensjonen.
- Anvendelse av banekoblingsmetoden for å demonstrere at Markov-kjeder raskt blandes (med Russ Bubley)
- Studie av kompleksiteten ved å telle problemer med tilfredshet av tilfredshet .
Priser og anerkjennelse
I 1991 mottok Martin Dyer sammen med Alan Frieze og Ravi Kannan Fulkersonprisen i diskret matematikk for sin artikkel i ACM-tidsskriftet. I 2013 tildelte EATCS ham EATCS-prisen .
Merknader og referanser
-
(in) " Martin E. Dyer " på nettstedet Mathematics Genealogy Project
-
Laudatio for EATCS-prisen.
-
Martin Dyer, Alan Frieze og Ravindran Kannan, “ En tilfeldig polynom-tidsalgoritme for tilnærming til volumet av konvekse legemer ”, Journal of the ACM , vol. 38, n o 1,1991, s. 1–17 ( DOI 10.1145 / 102782.102783 , les online )
-
Russ Bubley og Martin Dyer, “ Path coupling: a teknikk for å bevise rask blanding i Markov-kjeder ”, Proceedings of the 38th Annual Symposium on Foundations of Computer Science, IEEE ,
1997, s. 223–231 ( DOI 10.1109 / SFCS.1997.646111 , les online )
-
Fulkerson-prisen 1991
(fr) Denne artikkelen er helt eller delvis hentet fra den
engelske Wikipedia- artikkelen med tittelen
" Martin Dyer " ( se forfatterlisten ) .
Eksterne linker