Alan Michael Frieze (* 25. Oktober 1945 in London) ist ein britischer Informatiker.

Frieze studierte an der Universität Oxford (Bachelor-Abschluss 1966) und wurde 1975 an der Universität London bei Keith Wolfenden promoviert. 1968/69 forschte er (als Research Officer) bei British Rail und 1969/70 war er Programmierer bei ICL. 1970/71 war er Lecturer am Polytechnic of North London und 1972 bis 1987 lehrte er am Queen Mary College der Universität London. Er ist seit 1987 Professor an der Carnegie Mellon University.

Mit Martin Dyer und Ravindran Kannan fand er 1991 einen Polynomialzeitalgorithmus zur Berechnung der Volumina konvexer Körper in allen Dimensionen, wofür alle drei den Fulkerson-Preis erhielten. Zudem wurde die Arbeit bei der Verleihung des Knuth-Preises an Kannan als eine der herausragendsten Entwicklungen von Algorithmen hervorgehoben. Die Laufzeit aller vorher bekannten Algorithmen zur Volumenberechnung wuchsen exponentiell mit der Dimension. Ihr Algorithmus verwendet Markow-Ketten-Monte-Carlo-Algorithmen (MCMC) und ist eine der frühesten und wichtigsten Anwendungen dieser Technik bei Näherungsalgorithmen.

Mit Dyer leistete er wichtige Beiträge zur probabilistischen Analyse von Algorithmen in kombinatorischer Optimierung.

Mit Kannan fand er eine algorithmische Version des Regularitätslemmas von Endre Szemerédi. In ihrer Arbeit führten sie das schwache Regularitätslemma ein, das ein wichtiges kombinatorisches Werkzeug für verschiedene Algorithmen wurde (Streaming Algorithms, Graph Limits, Sublinear Algorithms).

1991 erhielt er den Fulkerson-Preis mit Dyer und Kannan. 1997 war er Guggenheim Fellow. 2014 wurde er als Plenarsprecher auf dem Internationalen Mathematikerkongress in Seoul ausgewählt (Random structures and algorithms). Er ist Fellow der American Mathematical Society.

Er ist seit 1969 mit Carol Frieze (geborene Mayfield) verheiratet, die ebenfalls Informatik an der Carnegie Mellon University lehrt. Mit ihr hat er zwei Kinder.

Einzelnachweise

  1. ↑ Lebensdaten nach American Men and Women of Science, Thomson Gale 2004
  2. ↑ Mathematics Genealogy Project
  3. ↑ Dyer, Frieze, Kannan A random polynomial-time algorithm for approximating the volume of convex bodies, Journal of the ACM, Band 38, 1991, S. 1–17
  4. ↑ Frieze, Kannan The regularity lemma and approximation schemes for dense problems, Proc. 37. Symposium Foundations of Computer Science (FOCS) 1996. Frieze, Kannan A simple algorithm for constructing Szemeredis regularity partition, Electronic J. Combinatorics, Band 6, 1999
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.