Eugene Lawler

Eugene Leighton (Gene) Lawler
Born1933 (1933)
DiedSeptember 2, 1994
NationalityAmerican
Scientific career
Fieldscomputer science, biology
Notable studentsDavid Shmoys, Tandy Warnow

Eugene Leighton (Gene) Lawler (1933 – September 2, 1994) was an American computer scientist and a professor of computer science at the University of California, Berkeley.[1][2]

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 applied mathematics in 1962 under the supervision of Anthony G. Oettinger with a dissertation entitled Some Aspects of Discrete Mathematical Programming.[1][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

  1. ^ a b c d e f g h 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, S2CID 62210683.
  2. ^ 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 Rice Univ, Corporate (1994), "In memoriam Eugene L. Lawler", SIGACT News, 25 (4): 108–109, doi:10.1145/190616.190626, S2CID 5267081.
  3. ^ a b Lawler, E. L. (1991), "Old stories", in Lenstra, J. K.; Rinnooy Kan, A. H. G.; Schrijver, A. (eds.), History of Mathematical Programming: A Collection of Personal Reminiscences, North-Holland, pp. 97–106.
  4. ^ Editorial staff (1995) In Memoriam: Eugene L. Lawler, SIAM Journal on Computing 24(1), 1-2.
  5. ^ a b Eugene Leighton Lawler at the Mathematics Genealogy Project.
  6. ^ a b c Karp, Richard (2003), A Personal View of Computer Science at Berkeley, EECS Department, University of California, Berkeley.
  7. ^ Theoretical computer science academic genealogy, Ian Parberry, 1996, retrieved 2010-09-17.
  8. ^ a b c Lenstra, Jan Karel; Schmoys, David (1998), "Preface", Mathematical Programming, 82 (1–2): 1, doi:10.1007/BF01585862.
  9. ^ Browne, Malcolm W. (November 7, 1979), "A Soviet discovery rocks world of mathematics: Russian's surprise problem-solving discovery reported", The New York Times.
  10. ^ 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.
  11. ^ 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.
  12. ^ Lawler, E. L. (1975), "Matroid intersection algorithms", Mathematical Programming, 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), "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, vol. 4, North-Holland, p. 287.
  14. ^ T'kindt, Vincent; Billaut, Jean-Charles (2002), Multicriteria scheduling: theory, models and algorithms, Springer-Verlag, p. 16, ISBN 978-3-540-43617-1.
  15. ^ 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 (eds.), Logistics of Production and Inventory, Handbooks in Operations Research and Management Science, vol. 4, North Holland, pp. 445–522.
  16. ^ Eugene L. Lawler Award, ACM, retrieved 2010-09-14.
  17. ^ 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.