https://wiki-de.moshellshocker.dns64.de/index.php?action=history&feed=atom&title=Jack_EdmondsJack Edmonds - Versionsgeschichte2026-05-27T08:27:58ZVersionsgeschichte dieser Seite in Wikipedia (Deutsch) – Lokale KopieMediaWiki 1.43.8https://wiki-de.moshellshocker.dns64.de/index.php?title=Jack_Edmonds&diff=2806565&oldid=previmported>Thomas Dresler: Kommasetzung2024-03-14T21:25:01Z<p>Kommasetzung</p>
<p><b>Neue Seite</b></p><div>[[Datei:Jack.Edmonds.jpg|mini|Jack Edmonds]]<br />
'''Jack R. Edmonds''' (* [[5. April]] [[1934]]) ist ein kanadischer Informatiker und Mathematiker, der sich mit [[Kombinatorische Optimierung|kombinatorischer Optimierung]] befasst.<br />
<br />
== Leben ==<br />
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]]. 1960 wurde er an der University of Maryland mit der Schrift ''A Combinatorial representation for oriented polyhedral surfaces'' promoviert.<ref>{{MathGenealogyProject|id=44142}} abgerufen am 13. März 2024.</ref> 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.<br />
<br />
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 (Graphentheorie)|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.<ref>Brian Hayes, Accidental Algorithms, American Scientist, Band 96, Januar/Februar 2008, S. 9–13</ref> 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 [[Matroid]]e und Optimale Verzweigungen (Optimum Branchings).<br />
<br />
Mit [[Ellis L. Johnson]] löste er das [[Briefträgerproblem]] (''Chinese Postman Problem'') mit [[Matching (Graphentheorie)|Matching]]-Methoden.<ref>Edmonds, Johnson ''Matching, Euler tours and the Chinese Postman'', Mathematical Programming, Band 5, 1973, S. 88–124</ref> Sie zeigten, dass es in polynomialer Zeit lösbar ist (im Gegensatz zu dem scheinbar ähnlichen, aber weit schwierigeren [[Problem des Handlungsreisenden]]).<br />
<br />
1985 erhielt er den [[John-von-Neumann-Theorie-Preis]].<br />
<br />
== Literatur ==<br />
*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<br />
== Schriften ==<br />
*Paths, trees and flowers, Canadian Journal of Mathematics, Band 17, 1965, S. 449–467<br />
*Matroids and the Greedy algorithm, Mathematical Programming, Band 1, 1971, S. 127–136<br />
*mit Richard Karp: Theoretical improvements in the algorithmic efficiency of network flow algorithms, Journal of the ACM, Band 19, 1972, S. 248–264<br />
<br />
== Weblinks ==<br />
* [https://zbmath.org/authors/edmonds.jack-r Jack R. Edmonds] in der Datenbank [[zbMATH]]<br />
<br />
== Einzelnachweise ==<br />
<references /><br />
<br />
{{Normdaten|TYP=p|GND=|LCCN=nb/2003/29180|VIAF=58590405|GNDfehlt=ja|GNDCheck=2020-04-21}}<br />
<br />
{{SORTIERUNG:Edmonds, Jack}}<br />
[[Kategorie:Informatiker]]<br />
[[Kategorie:Mathematiker (20. Jahrhundert)]]<br />
[[Kategorie:Hochschullehrer (University of Waterloo)]]<br />
[[Kategorie:Kanadier]]<br />
[[Kategorie:Geboren 1934]]<br />
[[Kategorie:Mann]]<br />
<br />
{{Personendaten<br />
|NAME=Edmonds, Jack<br />
|ALTERNATIVNAMEN=Edmonds, Jack R.<br />
|KURZBESCHREIBUNG=kanadischer Mathematiker und Informatiker<br />
|GEBURTSDATUM=5. April 1934<br />
|GEBURTSORT=<br />
|STERBEDATUM=<br />
|STERBEORT=<br />
}}</div>imported>Thomas Dresler