Jack R. Edmonds (* 5. April 1934) ist ein kanadischer Informatiker und Mathematiker, der sich mit kombinatorischer Optimierung befasst.

Edmonds studierte an der George Washington University mit dem Bachelorabschluss 1958 und an der University of Maryland mit dem Masterabschluss 1959. Danach arbeitete er bis 1969 in der Abteilung Operations Research am National Bureau of Standards unter Alan Goldman. Ab 1969 war er Professor an der University of Waterloo. Er lehrte dort bis zu seiner Emeritierung 1999, bis auf eine Zeit von 1991 bis 1993, in der er in einen Disput mit der Universität über einen vorgeblichen Rücktrittsbrief involviert war.

Von ihm und Richard M. Karp stammt der Algorithmus von Edmonds und Karp. 1965 veröffentlichte er den ersten polynomzeitlichen Algorithmus für das Matching-Problem in der Graphentheorie (Algorithmus von Edmonds), was zeigte dass das entsprechende Entscheidungsproblem in P ist. Das war auch die erste publizierte Diskussion der Unterscheidung zwischen polynomzeitlichen Algorithmen und solchen mit exponentieller Zeit. Bekannt ist er auch für den Struktursatz von Tibor Gallai und Edmonds (und Edmonds-Gallai-Zerlegung), der Maximum-Matchings beschreibt, für Beiträge zur Theorie der Matroide und Optimale Verzweigungen (Optimum Branchings).

Mit Ellis L. Johnson löste er das Briefträgerproblem (Chinese Postman Problem) mit Matching-Methoden. Sie zeigten, dass es in polynomialer Zeit lösbar ist (im Gegensatz zu dem scheinbar ähnlichen, aber weit schwierigeren Problem des Handlungsreisenden).

1985 erhielt er den John-von-Neumann-Theorie-Preis.

Literatur

  • David R. Lid (Herausgeber): A century of excellence in standards, measurement and technology: a chronicle of selected NBS/NIST 1901-2000, NIST Special Publications 958, Washington D. C. 2001

Schriften

  • Paths, trees and flowers, Canadian Journal of Mathematics, Band 17, 1965, S. 449–467
  • Matroids and the Greedy algorithm, Mathematical Programming, Band 1, 1971, S. 127–136
  • mit Richard Karp: Theoretical improvements in the algorithmic efficiency of network flow algorithms, Journal of the ACM, Band 19, 1972, S. 248–264

Einzelnachweise

  1. ↑ Brian Hayes, Accidental Algorithms, American Scientist, Band 96, Januar/Februar 2008, S. 9–13
  2. ↑ Edmonds, Johnson Matching, Euler tours and the Chinese Postman, Mathematical Programming, Band 5, 1973, S. 88–124
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.