Jack Edmonds - Jack Edmonds
Jack Edmonds | |
---|---|
Edmonds se svým NP rockem před svým domovem v kanadském Ontariu | |
narozený | John Robert Edmonds 5. dubna 1934 |
Alma mater | University of Maryland Univerzita George Washingtona Duke University |
Známý jako | NP Algoritmus Edmonds – Karp Edmonds – Gallaiho věta o rozkladu Cobhamova teze Blossom algoritmus Edmondsův algoritmus Polymatroid Průnik matroidů Edmondsova matice |
Ocenění | Cena teorie Johna von Neumanna (1985) |
Vědecká kariéra | |
Pole | Počítačová věda, matematika |
Instituce | University of Waterloo Národní institut pro standardy a technologie |
Doktorandi | Peyton Young William R. Pulleyblank Gilberto Calvillo Vives Mustafa Akgul Arnaldo Mandel Ephraim Korach Tom Jenkyns Victor Griffin Rick Giles Kathie Cameron Komei Fukuda William Cunningham Julian Araoz Durand |
Jack R. Edmonds (narozen 5. dubna 1934) je Američan-narozený a vzdělaný počítačový vědec a matematik který většinu svého života žil a pracoval v Kanadě. Zásadně přispěl do oblastí kombinatorická optimalizace, polyedrická kombinatorika, diskrétní matematika a teorie výpočtu. Byl příjemcem ceny Johna von Neumanna z roku 1985.
Ranná kariéra
Edmonds navštěvoval Duke University před dokončením vysokoškolského studia na univerzitě George Washingtona v roce 1957. Poté pokračoval v postgraduálním studiu na University of Maryland s prací o problému zabudování grafů do povrchů. V letech 1959 až 1969 pracoval v Národní institut pro standardy a technologie (tehdy Národní úřad pro standardy) a byl zakládajícím členem Alan Goldman Nově vytvořená sekce operačního výzkumu v roce 1961. Goldman se ukázal být rozhodujícím vlivem tím, že umožnil Edmondsovi pracovat na workshopu sponzorovaném společností RAND Corporation v Santa Monice v Kalifornii. Právě zde Edmonds poprvé představil svá zjištění týkající se definování třídy algoritmů, které by mohly běžet efektivněji. Většina učenců kombinatoriky se během této doby nezaměřovala na algoritmy. Edmonds je však k nim přitahoval a tato počáteční vyšetřování byla klíčovým vývojem pro jeho pozdější práci mezi matroidy a optimalizací. Roky 1961 až 1965 strávil tématem NP versus P a v roce 1966 vytvořil domněnky NP ≠ P a NP ∩ coNP = P.
Výzkum
Papír Edmonds 1965 „Cesty, stromy a květiny“ byl vynikajícím dokumentem, který původně navrhoval možnost vytvoření matematické teorie efektivních kombinatorických algoritmů. Jedním z jeho prvních a pozoruhodných příspěvků je algoritmus květu pro konstrukci maximální shody na grafech, objeveno v roce 1961[1] a publikováno v roce 1965.[2] Jednalo se o první algoritmus polynomiálního času pro maximální shodu v grafech. Jeho zobecnění na vážené grafy[3] byl koncepční průlom v používání lineární programování nápady v kombinatorická optimalizace. Uzavřelo to důležitost důkazů neboli „svědků“, že odpověď na instanci je ano, a existování důkazů nebo „svědků“, že odpověď na instanci je ne. V tomto článku o algoritmu květu Edmonds také charakterizuje proveditelné problémy jako ty řešitelné v polynomiálním čase; toto je jeden z počátků Cobham – Edmondsova práce.[4]
Průlom Cobham – Edmondsova práce, definoval pojem polynomiálního času charakterizující rozdíl mezi praktickým a nepraktickým algoritmem (v moderním přitažlivý problém nebo neřešitelný problém). Dnes se problémy řešitelné v polynomiálním čase nazývají třída složitosti PTIMEnebo jednoduše P.
Edmondova práce „Maximum Matching and a Polyhedron with 0-1 Vertices“ spolu s jeho předchozí prací poskytla úžasné polynomiálně-časové algoritmy pro konstrukci maximálních shody. Nejpozoruhodnější je, že tyto práce ukázaly, jak by dobrá charakterizace mnohostěnu spojená s problémem kombinatorické optimalizace mohla vést pomocí teorie duality lineárního programování ke konstrukci účinného algoritmu pro řešení tohoto problému.
Další mezník Edmonds je v oblasti matroidy. Pro všechny našel mnohostěnný popis klenout se nad stromy grafu a obecněji pro všechny nezávislé sady matroidů.[5] Na tomto základě, jako nové aplikaci lineárního programování do diskrétní matematiky, dokázal průnik matroidů věta, velmi obecná kombinatorická min-max věta[6][7] což v moderních termínech ukázalo, že problém průniku matroidů spočívá v obou NP a co-NP.
Edmonds je dobře známý pro své věty o algoritmy větvení s maximální hmotností[8] a balení okrajových disjunktních větví[9] a jeho práce s Richard Karp na rychlejší algoritmy toku. The Edmonds – Gallaiho věta o rozkladu popisuje konečné grafy z hlediska párování. Představil polymatroidy,[6] submodulární teče s Richardem Gilesem,[10] a podmínky nepořádek a blokátor při studiu hypergrafy.[1] Opakující se téma v jeho práci[11] je hledat algoritmy, jejichž časová složitost je polynomiálně omezena jejich velikostí vstupu a bitovou složitostí.[1]
Kariéra
Od roku 1969 s výjimkou let 1991–1993 působil na fakultní pozici na Katedře kombinatoriky a optimalizace na University of Waterloo je Matematická fakulta kde jeho výzkum zahrnoval kombinatorické optimalizační problémy a související mnohostěn. V této době dohlížel na doktorskou práci tuctu studentů.
V letech 1991 až 1993 byl účastníkem sporu („aféra Edmonds“) s University of Waterloo,[12][13] přičemž univerzita tvrdila, že předložený dopis představuje rezignační dopis, který Edmonds popřel.[14] Konflikt byl vyřešen v roce 1993 a on se vrátil na univerzitu.
Edmonds odešel z University of Waterloo v roce 1999.
Ceny a vyznamenání
Edmonds byl v roce 1985 příjemcem Cena teorie Johna von Neumanna.
V roce 2001 byl jeho dokument "Cesta, stromy a květiny" oceněn jako vynikající publikace Národní institut pro standardy a technologie ve svém slavnostním vydání A Century of Excellence in Measurements Standards and Technology
Byl zvolen do třídy 2002 Kolegové z Institut pro operační výzkum a vědy o řízení.[15]
V roce 2006 dánská královna udělila Edmondsovi čestný doktorát z University of Southern Denmark.
V roce 2014 byl oceněn jako Distinguished Scientist a uveden do Galerie Národního institutu pro standardy a technologie.
Pátý Aussois Seminář o kombinatorické optimalizaci v roce 2001 byl věnován jemu.[7]
Osobní život
Jackův syn Jeff Edmonds je profesorem informatiky na York University a jeho manželka Kathie Cameronová je profesorkou matematiky na Laurier University.
Viz také
Reference
- ^ A b C Edmonds, Jack (1991), „Záblesk nebe“, J.K. Lenstra; A.H.G. Rinnooy Kan; A. Schrijver (eds.), Historie matematického programování - sbírka osobních vzpomínek, CWI, Amsterdam a Severní Holandsko, Amsterdam, s. 32–54
- ^ Edmonds, Jack (1965). "Cesty, stromy a květiny". Umět. J. Math. 17: 449–467. doi:10.4153 / CJM-1965-045-4.
- ^ Edmonds, Jack (1965). Msgstr "Maximální shoda a mnohostěn s 0,1 vrcholy". Journal of Research of the National Bureau of Standards Section B. 69: 125–130.
- ^ Meurant, Gerard (2014). Algoritmy a složitost. str.str. 4. ISBN 978-0-08093391-7.
Říká se, že je problém proveditelný pokud to lze vyřešit v polynomiálním čase (jak je poprvé uvedeno v Edmonds [26] [1965, Cesty, stromy a květiny])).
- ^ Edmonds, Jack (1971). "Matroidy a chamtivý algoritmus". Matematika. Programování (Princeton Symposium Math. Prog. 1967). 1: 127–136.
- ^ A b Edmonds, Jack (1970), „Submodular functions, matroids, and certain polyhedra“, R. Guy; H. Hanam; N. Sauer; J. Schonheim (eds.), Kombinatorické struktury a jejich aplikace (konference 1969 Calgary Conference)Gordon and Breach, New York, s. 69–87.
- ^ A b Jünger, Michael; Reinelt, Gerhard; Rinaldi, Giovanni, eds. (2003), „Combinatorial Optimization - Eureka, You Shrink!“, Přednášky z informatikySpringer, 2570
- ^ Edmonds, Jack (1967). "Optimální větvení". J. Res. Nat. Bur. Standardy. 71B: 233–240.
- ^ Edmonds, Jack (1973), R. Rustin (ed.), „Edge-disjoint branchings“, Kombinatorické algoritmy, Monterey, Kalifornie, 1972: Algorithmics Press, New York: 91–96CS1 maint: umístění (odkaz)
- ^ Edmonds, Jack; Giles, Richard (1977), P.L. Kladivo; E.L. Johnson; B.H. Korte; G.L. Nemhauser (eds.), „A min-max relace pro submodulární funkce v grafech“, Studium programování celých čísel, Annals of Discrete Mathematics, Severní Holandsko, Amsterdam, 1: 185–204
- ^ Christoph Witzgall (2001), „Cesty, stromy a květiny“, Století excelence v oblasti měření, standardů a technologií (PDF), Národní institut pro standardy a technologii, s. 140–144, archivovány od originál (PDF) dne 2006-03-25, vyvoláno 2011-08-11
- ^ UW Gazette, 7. října 1992: CAUT vyzval případ Jacka Edmondse
- ^ Úvod editora Archivováno 2010-10-27 na Wayback Machine, in: Kenneth Westhues, ed., Workplace Mobbing in Academe: Reports from Twenty Universities, Lewiston: NY: The Edwin Mellen Press, 2004
- ^ Denní bulletin University of Waterloo, 5. března 2001: Konference ocenila Jacka Edmondse
- ^ Fellows: Abecední seznam, Institut pro operační výzkum a vědy o řízení, archivovány z originál dne 10.05.2019, vyvoláno 2019-10-09
externí odkazy
- Jack Edmonds na Matematický genealogický projekt
- Životopis Jacka Edmondse z Ústavu pro operační výzkum a vědy o řízení