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)^[1]. 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.^[2]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). ^[3] Er untersuchte auch Näherungsalgorithmen für Abzählprobleme aus dem Ising-Modell^[4], innerhalb der Polya´s Theorie von Abzählproblemen (wie denen von chemischen Verbindungen und Färbungen auf Graphen)^[5] und für Hamiltonsche Wege in Zufalls-Graphen^[6]

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

Weblinks

• Homepage

Einzelnachweise

1. ↑ Mathematics Genealogy Project
2. ↑ 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
3. ↑ Offizielle Seite zum Fulkerson Preis
4. ↑ Jerrum, Sinclair Polynomial time approximation algorithms for the Ising model, SIAM J. Computing, Band 22, 1993, S. 1087
5. ↑ Computational Polya theory, in Peter Rowlinson (Hrsg.) Surveys in Combinatorics, Stirling 1995, London Math. Society Lecture Notes, Cambridge University Press, 1995, S. 103-118
6. ↑ 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