Eugene Lawler

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

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, and as an electrical engineer at Sylvania from 1959 to 1961. 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. He then became a faculty member at the University of Michigan until 1971, when he moved to Berkeley.

Research Lawler was an expert on combinatorial optimization and a founder of the field, He also wrote (with D. E. Wood) a heavily cited 1966 survey on branch and bound algorithms, selected as a citation classic in 1987, Lawler was also the first to observe that matroid intersection can be solved in polynomial time.

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. Another later survey is also highly cited (over 1000 citations each in Google scholar).

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.

Awards and honors A special issue of the journal Mathematical Programming (vol. 82, issues 1–2) was dedicated in Lawler's honor in 1998.

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".

Books Combinatorial Optimization: Networks and Matroids (Holt, Rinehart, and Winston 1976, , republished by Dover Books in 2001, ). Lenstra and Shmoys write that this book is a classic and that "it helped to shape an emerging field of research". The Traveling Salesman Problem: a guided tour of combinatorial optimization (with J. K. Lenstra, A. H. G. Rinnooy Kan, and D. Shmoys, Wiley, 1985, ). Selected publications of Eugene L. Lawler (K. Aardal, J. K. Lenstra, F. Maffioli, and D. Shmoys, eds., CWI Tracts 126, Centrum Wiskunde & Informatica, 1999, ). Reprints of 26 of Lawler's research papers.