Jack Edmonds

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 . 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.