Eugene Leighton (Gene) Lawler | |
---|---|

Born | 1933 |

Died | September 2, 1994 |

Nationality | American |

Scientific career | |

Fields | computer science, biology |

Notable students | 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]}

## 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 Rice Univ, Corporate (1994), "In memoriam Eugene L. Lawler",*SIGACT News*,**25**(4): 108–109, doi:10.1145/190616.190626, S2CID 5267081. - ^
^{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. **^**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, S2CID 206801650.**^**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 (eds.),*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