Geburt |
5. April 1934 Washington |
---|---|
Staatsangehörigkeit | kanadisch |
Ausbildung | Universität von Maryland |
Aktivitäten | Mathematiker , Informatiker |
Arbeitete für | Universität von Waterloo |
---|---|
Feld | Kombinatorisch |
Unterscheidung | John-von-Neumann-Theoriepreis (1985) |
Jack R. Edmonds , geboren am5. April 1934ist ein kanadischer Mathematiker und theoretischer Informatiker , der als einer der wichtigsten Mitwirkenden auf dem Gebiet der kombinatorischen Optimierung gilt .
Edmonds studierte an der George Washington University, wo er 1958 einen Bachelor-Abschluss erhielt, und 1959 an der University of Maryland mit einem Master-Abschluss . Anschließend arbeitete er bis 1969 in der Abteilung für Operations Research am National Institute of Standards and Technology unter der Leitung von Alan J. Goldman (en) . 1969 wurde er zum Professor am Department of Combinatorial Optimization der Fakultät für Mathematik der University of Waterloo ernannt , wo er bis zu seiner Pensionierung 1999 unterrichtete, mit Ausnahme des Zeitraums zwischen 1991 und 1993.
Es waren Edmonds und Richard Karp , die 1972 den Algorithmus zur Berechnung des maximalen Durchflusses veröffentlichten, der jetzt als Edmonds-Karp-Algorithmus bezeichnet wird . 1965 veröffentlichte Edmonds "Pfade, Bäume und Blumen", den ersten polynomiellen Zeitalgorithmus für das Problem der Kopplung in der Graphentheorie: den Edmonds-Algorithmus für Kopplungen , auch " Blütenalgorithmus " genannt . Mit seinem zweiten Artikel („Maximale Übereinstimmung und ein Polyeder mit 0-1 Eckpunkten“) zu diesem Thema legt er die Grundlagen für die Wechselwirkung zwischen Polyedergeometrie und kombinatorischer Optimierung, um effiziente Algorithmen zu konstruieren.
Er ist auch bekannt für einen Struktursatz, der maximale Kopplungen beschreibt, die als Gallai-Edmonds-Zerlegung bezeichnet wird und von Tibor Gallai unabhängig demonstriert wird . Er hat auch in der Matroidentheorie gearbeitet , die zeigt, dass das Problem der Schnittmenge von Matroiden sowohl im NP als auch im Co-NP liegt .
Mit Ellis L. Johnson (in) löst Edmonds das Problem des chinesischen Postboten mit Kopplungsmethoden . Sie zeigen, dass das Problem in Polynomzeit gelöst werden kann, im Gegensatz zum Problem des Handlungsreisenden, das so aussieht, aber viel schwieriger ist.
Edmonds hat auch einen optimalen Anschluss; Der sogenannte Edmonds- oder Chu-Liu-Algorithmus ist ein Algorithmus zum Auffinden eines Spannbaums mit minimalem Gewicht (als optimale Verzweigung bezeichnet). es ist das Analogon des Spannbaums mit minimalem Gewicht. Der Algorithmus wurde unabhängig zuerst von Yoeng-Jin Chu und Tseng-Hong Liu (1965) und dann von Jack Edmonds (1967) vorgeschlagen.
Edmonds erhielt 1985 den John-von-Neumann-Theoriepreis . 2002 wurde er zum Fellow in der ersten INFORM- Fellow-Klasse gewählt. Zwischen 1970 und 1982 betreute Edmonds die Abschlussarbeiten von 14 Doktoranden an der University of Waterloo.