Jack Edmonds – Wikipedia

Posted on by
before-content-x4

Amerikanischer / kanadischer Mathematiker und Informatiker

Jack R. Edmonds (* 5. April 1934 in London) ist ein in Amerika geborener und ausgebildeter Informatiker und Mathematiker, der einen Großteil seines Lebens in Kanada gelebt und gearbeitet hat. Er hat grundlegende Beiträge zu den Bereichen kombinatorische Optimierung, polyedrische Kombinatorik, diskrete Mathematik und Computertheorie geleistet. Er erhielt 1985 den John-von-Neumann-Theoriepreis.

Frühe Karriere[edit]

Edmonds besuchte die Duke University, bevor er 1957 sein Grundstudium an der George Washington University abschloss. Danach absolvierte er ein Studium an der University of Maryland mit einer Arbeit über das Problem der Einbettung von Graphen in Oberflächen. Von 1959 bis 1969 arbeitete er am Nationalen Institut für Standards und Technologie (damals National Bureau of Standards) und war 1961 Gründungsmitglied der neu geschaffenen Operations Research Section von Alan Goldman. Goldman erwies sich als entscheidender Einflussfaktor, indem er Edmonds dies ermöglichte Arbeit in einem von der RAND Corporation gesponserten Workshop in Santa Monica, Kalifornien. Hier präsentierte Edmonds erstmals seine Erkenntnisse zur Definition einer Klasse von Algorithmen, die effizienter ausgeführt werden könnten. Die meisten Kombinatoriker konzentrierten sich in dieser Zeit nicht auf Algorithmen. Edmonds war jedoch von ihnen angezogen und diese ersten Untersuchungen waren Schlüsselentwicklungen für seine spätere Arbeit zwischen Matroiden und Optimierung. Er verbrachte die Jahre von 1961 bis 1965 mit dem Thema NP gegen P und brachte 1966 die Vermutungen NP ≠ P und NP ∩ coNP = P hervor.

Forschung[edit]

Edmonds 1965er Artikel „Paths, Trees and Flowers“ war ein herausragender Artikel, in dem zunächst die Möglichkeit vorgeschlagen wurde, eine mathematische Theorie effizienter kombinatorischer Algorithmen aufzustellen. Einer seiner frühesten und bemerkenswertesten Beiträge ist der 1961 entdeckte Blütenalgorithmus zur Konstruktion maximaler Übereinstimmungen auf Graphen[1] und 1965 veröffentlicht.[2] Dies war der erste Polynom-Zeit-Algorithmus für die maximale Übereinstimmung in Graphen. Seine Verallgemeinerung auf gewichtete Graphen[3] war ein konzeptioneller Durchbruch bei der Verwendung linearer Programmierideen bei der kombinatorischen Optimierung. Es besiegelte die Wichtigkeit von Beweisen oder “Zeugen”, dass die Antwort für eine Instanz Ja ist und es Beweise oder “Zeugen” gibt, dass die Antwort für eine Instanz Nein ist. In diesem Artikel über Blütenalgorithmen charakterisiert Edmonds auch mögliche Probleme als solche, die in Polynomzeit lösbar sind. Dies ist einer der Ursprünge der Cobham-Edmonds-These.[4]

Ein Durchbruch der Cobham-Edmonds-These war die Definition des Konzepts der Polynomzeit, das den Unterschied zwischen einem praktischen und einem unpraktischen Algorithmus charakterisiert (in modernen Begriffen ein nachvollziehbares Problem oder ein unlösbares Problem). In der Polynomzeit lösbare Probleme werden heute als Komplexitätsklasse bezeichnet PTIME, oder einfach P..

Edmonds Artikel „Maximale Übereinstimmung und ein Polyeder mit 0-1 Eckpunkten“ sowie seine früheren Arbeiten lieferten erstaunliche Polynom-Zeit-Algorithmen für die Konstruktion maximaler Übereinstimmungen. Insbesondere haben diese Arbeiten gezeigt, wie eine gute Charakterisierung des mit einem kombinatorischen Optimierungsproblem verbundenen Polyeders über die Dualitätstheorie der linearen Programmierung zur Konstruktion eines effizienten Algorithmus zur Lösung dieses Problems führen kann.

Weitere wegweisende Arbeiten von Edmonds liegen im Bereich der Matroiden. Er fand eine polyedrische Beschreibung für alle überspannenden Bäume eines Graphen und allgemeiner für alle unabhängigen Sätze einer Matroid.[5] Darauf aufbauend bewies er als neuartige Anwendung der linearen Programmierung auf die diskrete Mathematik den Matroid-Schnittpunktsatz, einen sehr allgemeinen kombinatorischen Min-Max-Satz[6][7] was in modernen Begriffen zeigte, dass das Matroid-Schnittpunkt-Problem sowohl im NP als auch im Co-NP lag.

Edmonds ist bekannt für seine Sätze über Verzweigungsalgorithmen mit maximalem Gewicht[8] und Packen von kantendisjunkten Verzweigungen[9] und seine Arbeit mit Richard Karp an schnelleren Flussalgorithmen. Der Edmonds-Gallai-Zerlegungssatz beschreibt endliche Graphen unter dem Gesichtspunkt von Übereinstimmungen. Er führte Polymatroide ein,[6]submodulare Strömungen mit Richard Giles,[10] und die Begriffe Unordnung und Blocker bei der Untersuchung von Hypergraphen.[1] Ein wiederkehrendes Thema in seiner Arbeit[11] besteht darin, nach Algorithmen zu suchen, deren zeitliche Komplexität polynomiell durch ihre Eingabegröße und Bitkomplexität begrenzt ist.[1]

Von 1969 an war er mit Ausnahme von 1991–1993 Fakultätsstelle am Institut für Kombinatorik und Optimierung der Fakultät für Mathematik der Universität von Waterloo, wo seine Forschung kombinatorische Optimierungsprobleme und damit verbundene Polyeder umfasste. In dieser Zeit betreute er die Doktorarbeit von einem Dutzend Studenten.

Von 1991 bis 1993 war er in einen Streit (“die Edmonds-Affäre”) mit der University of Waterloo verwickelt.[12][13] wobei die Universität behauptete, dass ein eingereichtes Schreiben ein Rücktrittsschreiben darstelle, das Edmonds bestritt.[14] Der Konflikt wurde 1993 gelöst und er kehrte an die Universität zurück.

Edmonds zog sich 1999 von der University of Waterloo zurück.

Auszeichnungen und Ehrungen[edit]

Edmonds erhielt 1985 den John von Neumann Theory Prize.

Im Jahr 2001 wurde seine Arbeit “Path, Trees and Flowers” vom National Institute of Standards and Technology in ihrer feierlichen Ausgabe von A Century of Excellence in Measurements Standards and Technology als herausragende Veröffentlichung ausgezeichnet

Er wurde 2002 in die Fellows-Klasse des Instituts für Operations Research und Management Sciences gewählt.[15]

2006 verlieh die Königin von Dänemark Edmonds die Ehrendoktorwürde der University of Southern Denmark.

2014 wurde er als Distinguished Scientist geehrt und in die Galerie des National Institute of Standards and Technology aufgenommen.

Ihm war der fünfte australische Workshop zur kombinatorischen Optimierung im Jahr 2001 gewidmet.[7]

Persönliches Leben[edit]

Jacks Sohn Jeff Edmonds ist Professor für Informatik an der York University und seine Frau Kathie Cameron ist Professorin für Mathematik an der Laurier University.

Siehe auch[edit]

Verweise[edit]

  1. ^ ein b c Edmonds, Jack (1991), “Ein Blick in den Himmel”, in JK Lenstra; AHG Rinnooy Kan; A. Schrijver (Hrsg.), Geschichte der mathematischen Programmierung – Eine Sammlung persönlicher Erinnerungen, CWI, Amsterdam und Nordholland, Amsterdam, S. 32–54
  2. ^
    Edmonds, Jack (1965). “Wege, Bäume und Blumen”. Können. J. Math. 17: 449–467. doi:10.4153 / CJM-1965-045-4.
  3. ^
    Edmonds, Jack (1965). “Maximale Übereinstimmung und ein Polyeder mit 0,1 Eckpunkten”. Journal of Research des National Bureau of Standards, Abschnitt B.. 69: 125–130.
  4. ^ Meurant, Gerard (2014). Algorithmen und Komplexität. p. p. 4. ISBN 978-0-08093391-7. Ein Problem soll sein möglich wenn es in Polynomzeit gelöst werden kann (wie zum ersten Mal in Edmonds angegeben [26] [1965, Paths, trees, and flowers])).
  5. ^
    Edmonds, Jack (1971). “Matroiden und der gierige Algorithmus”. Mathematik. Programmierung (Princeton Symposium Math. Prog. 1967). 1: 127–136.
  6. ^ ein b Edmonds, Jack (1970), “Submodulare Funktionen, Matroiden und bestimmte Polyeder”, in R. Guy; H. Hanam; N. Sauer; J. Schonheim (Hrsg.), Kombinatorische Strukturen und ihre Anwendungen (Proc. 1969 Calgary Conference)Gordon and Breach, New York, S. 69–87.
  7. ^ ein b
    Jünger, Michael; Reinelt, Gerhard; Rinaldi, Giovanni, Hrsg. (2003), “Kombinatorische Optimierung – Eureka, du schrumpfst!”, Vorlesungsunterlagen in Informatik, Springer, 2570
  8. ^
    Edmonds, Jack (1967). “Optimale Verzweigungen”. J. Res. Nat. Bur. Standards. 71B: 233–240.
  9. ^
    Edmonds, Jack (1973), R. Rustin (Hrsg.), “Edge-disjoint branchings”, Kombinatorische Algorithmen, Monterey, Kalifornien, 1972: Algorithmics Press, New York: 91–96CS1-Wartung: Standort (Link)
  10. ^
    Edmonds, Jack; Giles, Richard (1977), PL Hammer; EL Johnson; BH Korte; GL Nemhauser (Hrsg.), “Eine Min-Max-Beziehung für submodulare Funktionen in Graphen”, Studium der Integer-Programmierung, Annalen der diskreten Mathematik, Nordholland, Amsterdam, 1: 185–204
  11. ^ Christoph Witzgall (2001), “Wege, Bäume und Blumen”, Ein Jahrhundert der Exzellenz in Messungen, Standards und Technologie (PDF), Nationales Institut für Standards und Technologie, S. 140–144, archiviert von das Original (PDF) am 25.03.2006abgerufen 2011-08-11
  12. ^ UW Gazette, 7. Oktober 1992: CAUT hat den Fall Jack Edmonds angerufen
  13. ^ Einführung des Herausgebers Archiviert 27.10.2010 an der Wayback Machine, in: Kenneth Westhues, Hrsg., Workplace Mobbing in Academe: Berichte von 20 Universitäten, Lewiston: NY: The Edwin Mellen Press, 2004
  14. ^ Daily Bulletin der University of Waterloo, 5. März 2001: Konferenz ehrt Jack Edmonds
  15. ^ Fellows: Alphabetische Liste, Institut für Operations Research und Management Sciences, archiviert von das Original am 10.05.2019abgerufen 2019-10-09

Externe Links[edit]


after-content-x4