Jack Edmonds - Jack Edmonds
Jack Edmonds | |
|---|---|
 Edmonds ze swoim NP rock przed domem w Ontario w Kanadzie
| |
| Urodzić się |
John Robert Edmonds
5 kwietnia 1934 |
| Alma Mater |
Uniwersytet Maryland Uniwersytet Jerzego Waszyngtona Uniwersytet Duke |
| Znany z |
NP Edmonds-Karp algorytm Edmonds-Gallai rozkładu twierdzenie Cobham praca kwiat algorytm Edmonds algorytm Polymatroid matroid przecięcia Edmonds matrycy |
| Nagrody | Nagroda Teorii Johna von Neumanna (1985) |
| Kariera naukowa | |
| Pola | Informatyka, Matematyka |
| Instytucje |
Narodowy Instytut Standardów i Technologii Uniwersytetu Waterloo |
| Doktoranci | |
Jack R. Edmonds (ur. 5 kwietnia 1934) to urodzony w Ameryce i wykształcony informatyk i matematyk, który przez większość swojego życia mieszkał i pracował w Kanadzie. Dokonał zasadniczy wkład w dziedzinie optymalizacji kombinatorycznej , wieloboczne kombinatoryki , matematyki dyskretnej i teorii informatyki. Był laureatem Nagrody Teorii Johna von Neumanna w 1985 roku.
Wczesna kariera
Edmonds studiował na Duke University, zanim ukończył studia licencjackie na George Washington University w 1957 roku. Następnie kontynuował studia magisterskie na Uniwersytecie Maryland, pisząc pracę magisterską na temat problemu wbudowywania wykresów w powierzchnie. W latach 1959-1969 pracował w Narodowym Instytucie Standardów i Technologii (wówczas National Bureau of Standards) i był członkiem-założycielem nowo utworzonej Sekcji Badań Operacyjnych Alana Goldmana w 1961 roku. Goldman okazał się mieć decydujący wpływ, umożliwiając Edmonds do pracy w warsztacie sponsorowanym przez RAND Corporation w Santa Monica w Kalifornii. To tutaj Edmonds po raz pierwszy przedstawił swoje odkrycia dotyczące zdefiniowania klasy algorytmów, które mogłyby działać wydajniej. Większość badaczy kombinatoryki w tym czasie nie skupiała się na algorytmach. Jednak Edmonds został do nich przyciągnięty i te wstępne badania były kluczowymi osiągnięciami dla jego późniejszej pracy między matroidami a optymalizacją. Spędził lata od 1961 do 1965 na temat NP versus P, a w 1966 stworzył przypuszczenia NP P i NP ∩ coNP = P.
Badania
Artykuł Edmondsa z 1965 r. „Paths, Trees and Flowers” był wybitnym artykułem początkowo sugerującym możliwość ustanowienia matematycznej teorii wydajnych algorytmów kombinatorycznych. Jednym z jego najwcześniejszych i godnych uwagi wkładów jest algorytm kwitnienia służący do konstruowania maksymalnych dopasowań na wykresach, odkryty w 1961 i opublikowany w 1965. Był to pierwszy algorytm wielomianu dla maksymalnego dopasowania w grafach. Jego uogólnienie do grafów ważonych było przełomem koncepcyjnym w wykorzystaniu koncepcji programowania liniowego w optymalizacji kombinatorycznej . To przypieczętowało wagę istnienia dowodów lub „świadków”, że odpowiedź na dany przypadek brzmi „tak” i że istnieją dowody lub „świadkowie”, że odpowiedź na dany przypadek brzmi „nie”. W tym artykule o algorytmie rozkwitu Edmonds charakteryzuje również możliwe problemy jako te, które można rozwiązać w czasie wielomianowym; jest to jeden z początków tezy Cobhama-Edmondsa .
Przełomem w tezie Cobhama-Edmondsa było zdefiniowanie pojęcia czasu wielomianowego charakteryzującego różnicę między algorytmem praktycznym i niepraktycznym (we współczesnym ujęciu problem wykonalny lub problem niewykonalny ). Dzisiaj problemy rozwiązywalne w czasie wielomianowym nazywane są klasą złożoności PTIME lub po prostu P .
Artykuł Edmonda „Maximum Matching and a Polyhedron with 0-1 Vertices” wraz z jego poprzednią pracą dał zdumiewające wielomianowe algorytmy do konstruowania maksymalnych dopasowań. W szczególności prace te pokazały, w jaki sposób dobra charakterystyka wielościanu związanego z problemem optymalizacji kombinatorycznej może doprowadzić, poprzez teorię dualności programowania liniowego, do zbudowania wydajnego algorytmu rozwiązania tego problemu.
Dodatkowa przełomowa praca Edmondsa dotyczy matroidów . Znalazł wielościenny opis wszystkich drzew spinających grafu, a bardziej ogólnie dla wszystkich niezależnych zbiorów matroidu. Opierając się na tym, jako nowatorskim zastosowaniu programowania liniowego w matematyce dyskretnej, udowodnił twierdzenie o przecięciu matroidów , bardzo ogólne twierdzenie kombinatoryczne min-max, które we współczesnych warunkach wykazało, że problem przecięcia matroid leży zarówno w NP, jak i współ-NP. .
Edmonds jest dobrze znany ze swoich twierdzeń o algorytmach rozgałęzień o maksymalnej wadze i rozgałęzieniach rozłącznych na krawędzi oraz pracy z Richardem Karpem nad algorytmami o szybszym przepływie . Rozkładu twierdzenie Edmonds-Gallai opisano skończonych wykresy z punktu widzenia skojarzeń. Wprowadził polimatroidy , przepływy submodularne z Richardem Gilesem oraz terminy clutter i blocker w badaniu hipergrafów . Powracającym tematem w jego pracy jest poszukiwanie algorytmów, których złożoność czasowa jest wielomianowo ograniczona przez rozmiar wejściowy i złożoność bitową.
Kariera zawodowa
Od 1969 r., z wyjątkiem lat 1991-1993, zajmował stanowisko wydziału w Katedrze Kombinatoryki i Optymalizacji na Wydziale Matematyki Uniwersytetu Waterloo , gdzie jego badania obejmowały zagadnienia optymalizacji kombinatorycznej i związane z nimi wielościany. W tym czasie kierował pracą doktorską kilkunastu studentów.
Od 1991 do 1993 roku brał udział w sporze („afera Edmonds”) z University of Waterloo, w którym uniwersytet twierdził, że złożony list stanowił list rezygnacyjny, któremu Edmonds zaprzeczył. Konflikt został rozwiązany w 1993 roku i wrócił na uniwersytet.
Edmonds przeszedł na emeryturę z University of Waterloo w 1999 roku.
Nagrody i wyróżnienia
Edmonds był laureatem nagrody teoretycznej im . Johna von Neumanna w 1985 roku .
W 2001 r. jego artykuł „Ścieżka, drzewa i kwiaty” został wyróżniony jako Wybitna Publikacja przez Narodowy Instytut Standardów i Technologii w ich uroczystym wydaniu A Century of Excellence in Measurements Standards and Technology
Został wybrany do klasy 2002 Fellows z Instytutu Badań Operacyjnych i nauk o zarządzaniu .
W 2006 roku królowa Danii nadała Edmondsowi tytuł doktora honoris causa Uniwersytetu Południowej Danii .
W 2014 roku został uhonorowany tytułem Distinguished Scientist i wprowadzony do Galerii Narodowego Instytutu Standardów i Technologii.
Jemu poświęcono piąty warsztat Aussois na temat optymalizacji kombinatorycznej w 2001 roku.
Życie osobiste
Syn Jacka, Jeff Edmonds, jest profesorem informatyki na Uniwersytecie York , a jego żona Kathie Cameron jest profesorem matematyki na Uniwersytecie Laurier .
Zobacz też
Bibliografia
Zewnętrzne linki
- Jack Edmonds w projekcie genealogii matematyki
- Biografia Jacka Edmondsa z Instytutu Badań Operacyjnych i Nauk o Zarządzaniu