Eugene Lawler - Eugene Lawler

Eugene Leighton (Gene) Lawler
narozený1933 (1933)
Zemřel2. září 1994
Národnostamerický
Vědecká kariéra
Polepočítačová věda, biologie
Pozoruhodné studentyDavid Shmoys, Tandy Warnow

Eugene Leighton (Gene) Lawler (1933 - 2. září 1994) byl Američan počítačový vědec, profesor výpočetní techniky na University of California, Berkeley.[1][2]

Akademický život

Lawler přišel Harvard jako postgraduální student v roce 1954, po tříletém vysokoškolákovi B.S. program v matematice na Florida State University. V roce 1957 získal magisterský titul,[2] a přestal studovat, během nichž krátce navštěvoval právnickou školu a pracoval v americké armádě u brusírny,[3] a jako elektrotechnik ve společnosti Sylvania od roku 1959 do roku 1961.[2][4] V roce 1958 se vrátil na Harvard a dokončil Ph.D. v roce 1962 pod dohledem Anthony G. Oettinger s disertační prací s názvem Některé aspekty diskrétního matematického programování.[2][5] Poté se stal členem fakulty v Michiganská univerzita až do roku 1971, kdy se přestěhoval do Berkeley.[2] On odešel v roce 1994, krátce před jeho smrtí.[6]

V Berkeley byli Lawlerovými doktorandy Marshall Bern, Chip Martel Arvind Raghunathan, Arnie Rosenthal, Huzur Saran, David Shmoys, a Tandy Warnow.[5][7]

Výzkum

Lawler byl odborníkem na kombinatorická optimalizace a zakladatel oboru,[8] autor široce používané učebnice Kombinatorická optimalizace: Sítě a matroidy a spoluautor Problém obchodního cestujícího: prohlídka kombinatorické optimalizace s průvodcem. Hrál ústřední roli při záchraně elipsoidní metoda pro lineární programování z neznáma na Západě.[1][9] Napsal také (s D. E. Woodem) velmi citovaný průzkum z roku 1966 větev a svázaný algoritmy,[10] vybrán jako klasická citace v roce 1987,[2]a další vlivná raná kniha o dynamické programování s J. M. Moorem.[2][11] Lawler byl také první, kdo to pozoroval průnik matroidů lze vyřešit v polynomiální čas.[1][12]

The NP-úplnost důkazy pro dva z Karpových 21 NP-úplných problémů, režie Hamiltonovský cyklus a 3-dimenzionální shoda, byly připsány Karpem Lawlerovi.[1] Úplnost NP trojrozměrného párování je příkladem jednoho z Lawlerových oblíbených pozorování, „mystické síly dvojčata“:[1] pro mnoho kombinačních optimalizačních problémů, které lze parametrizovat celým číslem, lze problém vyřešit v polynomiální čas když je parametr dva, ale stane se NP úplným, když je parametr tři. Pro 3-dimenzionální shodu je řešitelná verze problému verze 2 shoda grafu; stejný fenomén vzniká ve složitosti 2-zbarvení a 3-zbarvení pro grafy, v problému průniku matroidů pro průniky dvou nebo tří matroidů a v 2-SAT a 3-SAT pro problémy s uspokojivostí. Lenstra[1] píše, že „Gene by vždy komentoval, že proto byl vytvořen svět dvou pohlaví.“

V 70. letech Lawler udělal velký pokrok v systematizaci algoritmů pro plánování pracovního obchodu.[1] Jeho průzkum z roku 1979 na toto téma představil tři pole zápis pro teoretické problémy s plánováním, který se (i přes existenci dřívějších notací) stal standardem při studiu plánovacích algoritmů.[13][14] Velmi citovaný je i další pozdější průzkum (každý přes 1 000 citací ve vědeckém výzkumu Google).[15]

Na konci 80. let Lawler přesunul své výzkumné zaměření na problémy výpočetní biologie, včetně rekonstrukce evoluční stromy a několik prací na zarovnání sekvence.[2]

Sociální aktivismus

Na jaře 1969, během volna v Berkeley, se Lawler zúčastnil a protest proti válce ve Vietnamu což vedlo k zatčení 483 demonstrantů, včetně Lawlera;[3] Richard Karp zachránil ho.[6]Karp připomíná Lawlera jako „sociální svědomí divize CS, vždy dbající na blahobyt studentů a zvláště na ženy, menšiny a studenty se zdravotním postižením“.[6]

Ceny a vyznamenání

Zvláštní vydání časopisu Matematické programování (ročník 82, čísla 1–2) byl věnován na Lawlerovu počest v roce 1998.[8]

The Cena ACM Eugena L. Lawlera je dán Sdružení pro výpočetní techniku každé dva roky za „humanitární příspěvky v rámci informatiky a informatiky“.[16]

Knihy

  • Kombinatorická optimalizace: Sítě a matroidy (Holt, Rinehart a Winston 1976,[17] ISBN  978-0-03-084866-7, publikoval Dover Books v roce 2001, ISBN  978-0-486-41453-9). Lenstra a Shmoys píší, že tato kniha je klasická a že „pomohla utvářet vznikající pole výzkumu“.[8]
  • Problém obchodního cestujícího: prohlídka kombinatorické optimalizace s průvodcem (s J. K. Lenstra, A. H. G. Rinnooy Kan a D. Shmoys, Wiley, 1985, ISBN  978-0-471-90413-7).
  • Vybrané publikace Eugena L. Lawlera (K. Aardal J. K. Lenstra, F. Maffioli a D. Shmoys, eds., CWI Tracts 126, Centrum Wiskunde & Informatica, 1999, ISBN  978-90-6196-484-1). Dotisky 26 Lawlerových výzkumných prací.

Reference

  1. ^ A b C d E F G Lenstra, Jan Karel (1998), „Mystická síla dvojčata: in memoriam Eugene L. Lawler“, Journal of Scheduling, 1 (1): 3–14, doi:10.1002 / (SICI) 1099-1425 (199806) 1: 1 <3 :: AID-JOS1> 3.0.CO; 2-B.
  2. ^ A b C d E F G h Gusfield, Dan; Shmoys, Davide; Lenstra, Jan Karel; Warnow, Tandy (1994), „In Memoriam Eugene L. Lawler“, Journal of Computational Biology, 1 (4): 255–256, doi:10.1089 / cmb.1994.1.255. Přetištěno Rice Univ, Corporate (1994), „In memoriam Eugene L. Lawler“, Novinky SIGACT, 25 (4): 108–109, doi:10.1145/190616.190626, S2CID  5267081.
  3. ^ A b Lawler, E. L. (1991), "Staré příběhy", v Lenstra, J. K.; Rinnooy Kan, A. H. G.; Schrijver, A. (eds.), Historie matematického programování: Sbírka osobních vzpomínek, Severní Holandsko, str. 97–106.
  4. ^ Redakční tým (1995) In Memoriam: Eugene L. Lawler, SIAM Journal on Computing 24(1), 1-2.
  5. ^ A b Eugene Leighton Lawler na Matematický genealogický projekt.
  6. ^ A b C Karp, Richard (2003), Osobní pohled na informatiku v Berkeley, Oddělení EECS, University of California, Berkeley.
  7. ^ Teoretická informatika, akademická genealogie „Ian Parberry, 1996, vyvoláno 17. 9. 2010.
  8. ^ A b C Lenstra, Jan Karel; Schmoys, David (1998), „Předmluva“, Matematické programování, 82 (1–2): 1, doi:10.1007 / BF01585862.
  9. ^ Browne, Malcolm W. (7. listopadu 1979), „Sovětský objev otřásl světem matematiky: objev ruského překvapení při řešení problémů hlášen“, New York Times.
  10. ^ Lawler, E. L .; Wood, D. E. (1966), "Metody větvení a vazby: průzkum", Operační výzkum, 14 (4): 699–719, doi:10.1287 / opre.14.4.699, JSTOR  168733.
  11. ^ Lawler, E. L .; Moore, J. M. (1969), „Funkční rovnice a její aplikace na alokaci zdrojů a problémy se sekvenováním“, Věda o řízení, 16 (1): 77–84, doi:10,1287 / mnsc.16.1.77, JSTOR  2628367.
  12. ^ Lawler, E. L. (1975), „Alroid algoritmy Matroid“, Matematické programování, 9 (1): 31–56, doi:10.1007 / BF01681329, S2CID  206801650.
  13. ^ Graham, Ronald L.; Lawler, Eugene L .; Lenstra, Jan K.; Rinnooy Kan, A. H. G. (1979), „Optimalizace a aproximace v deterministickém řazení a plánování: průzkum“, Diskrétní optimalizace I: sborník pokročilého výzkumného ústavu pro diskrétní optimalizaci a systémové aplikace, Annals of Discrete Mathematics, 4, Severní Holandsko, s. 287.
  14. ^ T'kindt, Vincent; Billaut, Jean-Charles (2002), Multikriteriální plánování: teorie, modely a algoritmySpringer-Verlag, str. 16, ISBN  978-3-540-43617-1.
  15. ^ Lawler, Eugene L .; Lenstra, Jan K.; Rinnooy Kan, A. H. G.; Shmoys, David B. (1993), „Sekvenování a plánování: algoritmy a složitost“, Graves, S. C .; Rinnooy Kan, A. H. G.; Zipkin, Paul Herbert (eds.), Logistika výroby a zásobPříručky v operačním výzkumu a vědě o řízení, 4, Severní Holandsko, str. 445–522.
  16. ^ Cena Eugena L. Lawlera, ACM, vyvoláno 2010-09-14.
  17. ^ Bellman, R. E. (1978). "Posouzení: Kombinovaná optimalizace: sítě a matroidyautor: Eugene L. Lawler ". Býk. Amer. Matematika. Soc. 84 (3): 461–463. doi:10.1090 / s0002-9904-1978-14493-0.

externí odkazy