Eugeniusz Lawler - Eugene Lawler

Eugene Leighton (Gene) Lawler
Urodzić się 1933 ( 1933 )
Zmarł 2 września 1994
Narodowość amerykański
Kariera naukowa
Pola informatyka , biologia
Znani studenci David Shmoys , Tandy Warnow

Eugene Leighton (Gene) Lawler (1933 – 2 września 1994) był amerykańskim informatykiem i profesorem informatyki na Uniwersytecie Kalifornijskim w Berkeley .

Życie akademickie

Lawler przyjechał na Harvard jako doktorant w 1954 roku, po trzyletnim programie licencjackim z matematyki na Uniwersytecie Stanowym Florydy . Uzyskał tytuł magistra w 1957 r. i zrobił sobie przerwę w nauce, podczas której na krótko poszedł do szkoły prawniczej i pracował w armii amerykańskiej, w firmie produkującej ściernice oraz jako inżynier elektryk w Sylvanii w latach 1959-1961. powrócił na Harvard w 1958 roku i ukończył doktorat. w matematyce stosowanej w 1962 pod kierunkiem Anthony'ego G. Oettingera z rozprawą zatytułowaną Niektóre aspekty programowania matematycznego dyskretnego . Następnie został członkiem wydziału na Uniwersytecie Michigan do 1971, kiedy przeniósł się do Berkeley. Przeszedł na emeryturę w 1994 roku, krótko przed śmiercią.

W Berkeley wśród doktorantów Lawlera byli Marshall Bern, Chip Martel , Arvind Raghunathan, Arnie Rosenthal, Huzur Saran, David Shmoys i Tandy Warnow .

Badania

Lawler był ekspertem w dziedzinie optymalizacji kombinatorycznej i twórcą tej dziedziny, autorem powszechnie używanego podręcznika Combinatorial Optimization: Networks and Matroids oraz współautorem The Traveling Salesman Problem: przewodnik po optymalizacji kombinatorycznej . Odegrał kluczową rolę w ratowaniu elipsoidalnej metody programowania liniowego przed zapomnieniem na Zachodzie. Napisał również (wraz z DE Woodem) często cytowaną ankietę z 1966 roku na temat algorytmów rozgałęzionych i powiązanych , wybraną jako klasyka cytowań w 1987 roku, a także inny wpływowy wczesny artykuł na temat programowania dynamicznego z JM Moore'em. Lawler był również pierwszym, który zauważył, że przecięcie matroid może być rozwiązywane w czasie wielomianowym .

W NP kompletności dowody na dwóch 21 NP-zupełny problemów Karp jest , skierowany Hamiltona stopnia i dopasowywania 3-wymiarowej , zostały zapisane za Karp do Lawler. NP-zupełność dopasowania trójwymiarowego jest przykładem jednej z ulubionych obserwacji Lawlera, „mistycznej potęgi dwoistości”: w przypadku wielu problemów optymalizacji kombinatorycznej, które można sparametryzować liczbą całkowitą, problem można rozwiązać w czasie wielomianowym, gdy parametr wynosi dwa, ale staje się NP-zupełny, gdy parametr wynosi trzy. W przypadku dopasowywania trójwymiarowego wariantem problemu z parametrem 2, który można rozwiązać, jest dopasowywanie grafu ; to samo zjawisko pojawia się w złożoności 2-kolorowania i 3-kolorowania dla wykresów, w problemie przecięcia matroidów dla przecięć dwóch lub trzech matroidów oraz w 2-SAT i 3-SAT dla problemów spełnialności . Lenstra pisze, że „Gene niezmiennie komentował, że właśnie dlatego wymyślono świat dwóch płci”.

W latach 70. Lawler poczynił wielkie postępy w systematyzowaniu algorytmów planowania pracy w sklepie . Jego ankieta na ten temat z 1979 r. wprowadziła notację trójpolową do teoretycznego planowania problemów , która (pomimo istnienia wcześniejszych notacji) stała się standardem w badaniach algorytmów szeregowania. Inna późniejsza ankieta jest również wysoko cytowana (ponad 1000 cytowań w Google research).

Pod koniec lat osiemdziesiątych Lawler przeniósł swoje badania na problemy biologii obliczeniowej , w tym rekonstrukcję drzew ewolucyjnych i kilka prac dotyczących dopasowywania sekwencji .

Aktywizm społeczny

Wiosną 1969 roku, podczas urlopu naukowego w Berkeley, Lawler brał udział w proteście przeciwko wojnie w Wietnamie , w wyniku którego aresztowano 483 protestujących, w tym Lawlera; Richard Karp wykupił go za kaucją. Karp wspomina Lawlera jako „sumienie społeczne Wydziału CS, zawsze troszczące się o dobro studentów i szczególnie troszczące się o kobiety, mniejszości i niepełnosprawnych studentów”.

Nagrody i wyróżnienia

Specjalny numer czasopisma Mathematical Programming (vol. 82, numery 1-2) został poświęcony na cześć Lawlera w 1998 roku.

Nagroda ACM Eugene L. Lawler Award jest przyznawana przez Association for Computing Machinery co dwa lata za „humanitarny wkład w informatykę i informatykę”.

Książki

  • Optymalizacja kombinatoryczna: Sieci i Matroids (Holt, Rinehart i Winston 1976, ISBN  978-0-03-084866-7 , ponownie opublikowane przez Dover Books w 2001 r., ISBN  978-0-486-41453-9 ). Lenstra i Shmoys piszą, że ta książka jest klasykiem i że „pomogła ukształtować rodzącą się dziedzinę badań”.
  • The Travelling Salesman Problem: oprowadzanie po optymalizacji kombinatorycznej (z JK Lenstrą , AHG Rinnooy Kanem i D. Shmoysem, Wiley, 1985, ISBN  978-0-471-90413-7 ).
  • Wybrane publikacje Eugene'a L. Lawlera ( red. K. Aardal , JK Lenstra, F. Maffioli i D. Shmoys , CWI Tracts 126, Centrum Wiskunde & Informatica , 1999, ISBN  978-90-6196-484-1 ). Przedruki 26 artykułów naukowych Lawlera.

Bibliografia

Zewnętrzne linki