Eugene Lawler
Eugene Leighton (Gene) Lawler | |
---|---|
Born | 1933 |
Died | September 2, 1994 |
Nationality | American |
Scientific career | |
Fields | computer science, biology |
Notable students | Arvind Raghunathan, David Shmoys, Tandy Warnow |
Eugene Leighton (Gene) Lawler (1933 – September 2, 1994) was an American computer scientist, a professor of computer science at the University of California, Berkeley.^{[1]}^{[2]}
Contents
Academic life
Lawler came to Harvard as a graduate student in 1954, after a three-year undergraduate B.S. program in Mathematics at Florida State University. He received a master's degree in 1957,^{[2]} and took a hiatus in his studies, during which he briefly went to law school and worked in the U.S. Army, at a grinding wheel company,^{[3]} and as an electrical engineer at Sylvania from 1959 to 1961.^{[2]}^{[4]} He returned to Harvard in 1958, and completed his Ph.D. in 1962 under the supervision of Anthony G. Oettinger with a dissertation entitled Some Aspects of Discrete Mathematical Programming.^{[2]}^{[5]} He then became a faculty member at the University of Michigan until 1971, when he moved to Berkeley.^{[2]} He retired in 1994, shortly before his death.^{[6]}
At Berkeley, Lawler's doctoral students included Marshall Bern, Chip Martel, Arvind Raghunathan, Arnie Rosenthal, Huzur Saran, David Shmoys, and Tandy Warnow.^{[5]}^{[7]}
Research
Lawler was an expert on combinatorial optimization and a founder of the field,^{[8]} the author of the widely used textbook Combinatorial Optimization: Networks and Matroids and coauthor of The Traveling Salesman Problem: a guided tour of combinatorial optimization. He played a central role in rescuing the ellipsoid method for linear programming from obscurity in the West.^{[1]}^{[9]} He also wrote (with D. E. Wood) a heavily cited 1966 survey on branch and bound algorithms,^{[10]} selected as a citation classic in 1987,^{[2]} and another influential early paper on dynamic programming with J. M. Moore.^{[2]}^{[11]} Lawler was also the first to observe that matroid intersection can be solved in polynomial time.^{[1]}^{[12]}
The NP-completeness proofs for two of Karp's 21 NP-complete problems, directed Hamiltonian cycle and 3-dimensional matching, were credited by Karp to Lawler.^{[1]} The NP-completeness of 3-dimensional matching is an example of one of Lawler's favorite observations, the "mystical power of twoness":^{[1]} for many combinatorial optimization problems that can be parametrized by an integer, the problem can be solved in polynomial time when the parameter is two but becomes NP-complete when the parameter is three. For 3-dimensional matching, the solvable parameter-2 version of the problem is graph matching; the same phenomenon arises in the complexities of 2-coloring and 3-coloring for graphs, in the matroid intersection problem for intersections of two or three matroids, and in 2-SAT and 3-SAT for satisfiability problems. Lenstra^{[1]} writes that "Gene would invariably comment that this is why a world with two sexes has been devised."
During the 1970s, Lawler made great headway in systematizing algorithms for job shop scheduling.^{[1]} His 1979 survey on the subject introduced the three-field notation for theoretic scheduling problems, which (despite the existence of earlier notations) became standard in the study of scheduling algorithms.^{[13]}^{[14]} Another later survey is also highly cited (over 1000 citations each in Google scholar).^{[15]}
In the late 1980s, Lawler shifted his research focus to problems of computational biology, including the reconstruction of evolutionary trees and several works on sequence alignment.^{[2]}
Social activism
In Spring 1969, while on sabbatical in Berkeley, Lawler took part in a protest against the Vietnam War that led to the arrests of 483 protesters, including Lawler;^{[3]} Richard Karp bailed him out.^{[6]} Karp recalls Lawler as "the social conscience of the CS Division, always looking out for the welfare of students and especially concerned for women, minorities and handicapped students".^{[6]}
Awards and honors
A special issue of the journal Mathematical Programming (vol. 82, issues 1–2) was dedicated in Lawler's honor in 1998.^{[8]}
The ACM Eugene L. Lawler Award is given by the Association for Computing Machinery every two years for "humanitarian contributions within computer science and informatics".^{[16]}
Books
- Combinatorial Optimization: Networks and Matroids (Holt, Rinehart, and Winston 1976,^{[17]} ISBN 978-0-03-084866-7, republished by Dover Books in 2001, ISBN 978-0-486-41453-9). Lenstra and Shmoys write that this book is a classic and that "it helped to shape an emerging field of research".^{[8]}
- The Traveling Salesman Problem: a guided tour of combinatorial optimization (with J. K. Lenstra, A. H. G. Rinnooy Kan, and D. Shmoys, Wiley, 1985, ISBN 978-0-471-90413-7).
- Selected publications of Eugene L. Lawler (K. Aardal, J. K. Lenstra, F. Maffioli, and D. Shmoys, eds., CWI Tracts 126, Centrum Wiskunde & Informatica, 1999, ISBN 978-90-6196-484-1). Reprints of 26 of Lawler's research papers.
References
- ^ ^{a} ^{b} ^{c} ^{d} ^{e} ^{f} ^{g} Lenstra, Jan Karel (1998), "The mystical power of twoness: 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.
- ^ ^{a} ^{b} ^{c} ^{d} ^{e} ^{f} ^{g} ^{h} Gusfield, Dan; Shmoys, David; 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. Reprinted in "In memoriam Eugene L. Lawler", SIGACT News, 25 (4): 108–109, 1994, doi:10.1145/190616.190626.
- ^ ^{a} ^{b} Lawler, E. L. (1991), "Old stories", in Lenstra, J. K.; Rinnooy Kan, A. H. G.; Schrijver, A., History of Mathematical Programming: A Collection of Personal Reminiscences, North-Holland, pp. 97–106.
- ^ Editorial staff (1995) In Memoriam: Eugene L. Lawler, SIAM Journal on Computing 24(1), 1-2.
- ^ ^{a} ^{b} Eugene Leighton Lawler at the Mathematics Genealogy Project.
- ^ ^{a} ^{b} ^{c} Karp, Richard (2003), A Personal View of Computer Science at Berkeley, EECS Department, University of California, Berkeley.
- ^ Theoretical computer science academic genealogy, Ian Parberry, 1996, retrieved 2010-09-17.
- ^ ^{a} ^{b} ^{c} Lenstra, Jan Karel; Schmoys, David (1998), "Preface", Mathematical Programming, 82 (1–2): 1, doi:10.1007/BF01585862.
- ^ Browne, Malcolm W. (November 7, 1979), "A Soviet discovery rocks world of mathematics: Russian's surprise problem-solving discovery reported", New York Times.
- ^ Lawler, E. L.; Wood, D. E. (1966), "Branch-and-bound methods: A survey", Operations Research, 14 (4): 699–719, doi:10.1287/opre.14.4.699, JSTOR 168733.
- ^ Lawler, E. L.; Moore, J. M. (1969), "A functional equation and its application to resource allocation and sequencing problems", Management Science, 16 (1): 77–84, doi:10.1287/mnsc.16.1.77, JSTOR 2628367.
- ^ Lawler, E. L. (1975), "Matroid intersection algorithms", Mathematical Programming, 9 (1): 31–56, doi:10.1007/BF01681329.
- ^ Graham, Ronald L.; Lawler, Eugene L.; Lenstra, Jan K.; Rinnooy Kan, A. H. G. (1979), "Optimization and approximation in deterministic sequencing and scheduling: a survey", Discrete optimization I: proceedings of the Advanced research institute on discrete optimization and systems applications, Annals of Discrete Mathematics, 4, North-Holland, p. 287.
- ^ T'kindt, Vincent; Billaut, Jean-Charles (2002), Multicriteria scheduling: theory, models and algorithms, Springer-Verlag, p. 16, ISBN 978-3-540-43617-1.
- ^ Lawler, Eugene L.; Lenstra, Jan K.; Rinnooy Kan, A. H. G.; Shmoys, David B. (1993), "Sequencing and scheduling: algorithms and complexity", in Graves, S. C.; Rinnooy Kan, A. H. G.; Zipkin, Paul Herbert, Logistics of Production and Inventory, Handbooks in Operations Research and Management Science, 4, North Holland, pp. 445–522.
- ^ Eugene L. Lawler Award, ACM, retrieved 2010-09-14.
- ^ Bellman, R. E. (1978). "Review: Combinatioral optimization: networks and matroids, by Eugene L. Lawler". Bull. Amer. Math. Soc. 84 (3): 461–463. doi:10.1090/s0002-9904-1978-14493-0.
External links
- Lawler in 1977, from the Oberwolfach photo collection