Mark Jerrum

Mark Richard Jerrum (* 1955) ist ein britischer Informatiker.

Jerrum wurde 1981 bei Leslie Valiant an der University of Edinburgh promoviert (On the complexity of evaluating multivariate polynomials)<ref>Mathematics Genealogy Project</ref>. Er war Professor in Edinburgh und ist Professor für Reine Mathematik am Queen Mary College der Universität London.

Jerrum befasst sich mit Kombinatorik, Komplexitätstheorie und stochastischen Prozessen, insbesondere mit randomisierten Algorithmen und Mischungszeiten von Markow-Ketten in kombinatorischen und geometrischen Problemen. Ende der 1980er Jahre untersuchte er mit seinem Studenten Alistair Sinclair, der bei ihm 1988 in Edinburgh promoviert wurde, Mischungseigenschaften von Markow-Ketten und konstruierte damit Monte Carlo Markow-Ketten-Näherungsalgorithmen für Abzählprobleme wie der von Matchings und damit zusammenhängend der Berechnung der Permanente, einem nach Ergebnissen von Valiant innerhalb der Komplexitätstheorie schwierigen Problem.<ref>Jerrum, Sinclair Approximate counting, uniform generation and rapidly mixing Markov chains, Information and Computation, Band 82, 1988, S. 93–133, Jerrum, Sinclair Approximating the permanent, SIAM Journal on Computing, Band 18, 1989, S. 1145–1178</ref> 1996 erhielten beide dafür den Gödel-Preis. 2006 erhielt er mit Alistair Sinclair und Eric Vigoda den Fulkerson-Preis für die Angabe eines polynomzeitlichen probabilistischen Näherungs-Algorithmus zur Berechnung der Permanente einer Matrix mit nicht negativen Elementen (A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries, Journal of the ACM, Band 51, 2004, S. 671–697).<ref>Offizielle Seite zum Fulkerson-Preis</ref> Er untersuchte auch Näherungsalgorithmen für Abzählprobleme aus dem Ising-Modell<ref>Jerrum, Sinclair Polynomial time approximation algorithms for the Ising model, SIAM J. Computing, Band 22, 1993, S. 1087</ref>, innerhalb der Polya´s Theorie von Abzählproblemen (wie denen von chemischen Verbindungen und Färbungen auf Graphen)<ref>Computational Polya theory, in Peter Rowlinson (Hrsg.) Surveys in Combinatorics, Stirling 1995, London Math. Society Lecture Notes, Cambridge University Press, 1995, S. 103–118</ref> und für Hamiltonsche Wege in Zufalls-Graphen.<ref>A. Frieze, Jerrum, M. Molloy, R. Robinson, N. Wormald Generating and counting Hamilton cycles in random regular graphs, Journal of Algorithms, Band 21, 1996, S. 176–198</ref>

Schriften

• Counting, sampling and integrating: algorithms and complexity, Birkhäuser 2003
• mit Sinclair The Markov chain Monte Carlo Method: an approach to approximate counting and integrating, in Dorit Hochbaum (Hrsg.) Approximate algorithms for NP hard problems, PWS Publishing 1997

Einzelnachweise

<references />

Weblinks

• Homepage

{{#ifeq: p | p | | {{#if: 12443133Xn/2002/15532423074277 | |

}} }}{{#ifeq:||{{#if: | [[Kategorie:Wikipedia:GND fehlt {{#invoke:Str|left|{{{GNDCheck}}}|7}}]] }}{{#if: | {{#if: | | }} }} }}{{#if: | {{#ifeq: 0 | 2 | | }} }}{{#if: | {{#ifeq: 0 | 2 | | }} }}{{#ifeq: p | p | {{#if: 12443133X | | {{#if: {{#statements:P227}} | | }} }} }}{{#ifeq: p | p | {{#if: 12443133X | {{#if: {{#invoke:Wikidata|pageId}} | {{#if: {{#statements:P227}} | | }} }} }} }}{{#ifeq: p | p | {{#if: n/2002/155324 | | {{#if: {{#statements:P244}} | | }} }} }}{{#ifeq: p | p | {{#if: n/2002/155324 | {{#if: {{#invoke:Wikidata|pageId}} | {{#if: {{#statements:P244}} | | }} }} }} }}{{#ifeq: p | p | {{#if: 23074277 | | {{#if: {{#statements:P214}} | | }} }} }}{{#ifeq: p | p | {{#if: 23074277 | {{#if: {{#invoke:Wikidata|pageId}} | {{#if: {{#statements:P214}} | | }} }} }} }}Vorlage:Wikidata-Registrierung

{{#if: Jerrum, Mark | {{#if: Jerrum, Mark Richard | {{#if: britischer Informatiker | {{#if: 1955 | {{#if: | {{#if: | {{#if: |