Eugene Lawler

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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]

Academic life[edit]

Lawler came to Harvard as a graduate student in 1954, after a three-year undergraduate program at a southern university. He received a masters 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]


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[edit]

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[edit]

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]



  1. ^ 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 .
  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 "In memoriam Eugene L. Lawler", SIGACT News 25 (4), 1994: 108–109, doi:10.1145/190616.190626 .
  3. ^ 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 .
  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", 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 .
  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 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, Logistics of Production and Inventory, Handbooks in Operations Research and Management Science 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. 

External links[edit]