Eugene Leighton (Gene) Lawler (1933 – September 2, 1994) was an American
computer scientist
A computer scientist is a scientist who specializes in the academic study of computer science.
Computer scientists typically work on the theoretical side of computation. Although computer scientists can also focus their work and research on ...
and a professor of computer science at the
University of California, Berkeley
The University of California, Berkeley (UC Berkeley, Berkeley, Cal, or California), is a Public university, public Land-grant university, land-grant research university in Berkeley, California, United States. Founded in 1868 and named after t ...
.
[.][. Reprinted in .]
Academic life
Lawler came to
Harvard
Harvard University is a private Ivy League research university in Cambridge, Massachusetts, United States. Founded in 1636 and named for its first benefactor, the Puritan clergyman John Harvard, it is the oldest institution of higher lear ...
as a graduate student in 1954, after a three-year undergraduate B.S. program in mathematics at
Florida State University
Florida State University (FSU or Florida State) is a Public university, public research university in Tallahassee, Florida, United States. It is a senior member of the State University System of Florida and a preeminent university in the s ...
. He received a master's degree in 1957,
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,
[.] and as an electrical engineer at
Sylvania from 1959 to 1961.
[Editorial staff (1995) ''In Memoriam: Eugene L. Lawler'', ]SIAM Journal on Computing
The ''SIAM Journal on Computing'' is a scientific journal focusing on the mathematical and formal aspects of computer science. It is published by the Society for Industrial and Applied Mathematics (SIAM).
Although its official ISO abbreviation i ...
24(1), 1-2. 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
The University of Michigan (U-M, U of M, or Michigan) is a public university, public research university in Ann Arbor, Michigan, United States. Founded in 1817, it is the oldest institution of higher education in the state. The University of Mi ...
until 1971, when he moved to Berkeley.
He retired in 1994, shortly before his death.
At Berkeley, Lawler's doctoral students included Marshall Bern,
Chip Martel, Arvind Raghunathan, Arnie Rosenthal, Huzur Saran,
David Shmoys, and
Tandy Warnow.
Research
Lawler was an expert on
combinatorial optimization
Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combina ...
and a founder of the field,
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
In mathematical optimization, the ellipsoid method is an iterative method for convex optimization, minimizing convex functions over convex sets. The ellipsoid method generates a sequence of ellipsoids whose volume uniformly decreases at every ste ...
for linear programming from obscurity in the West.
He also wrote (with D. E. Wood) a heavily cited 1966 survey on
branch and bound
Branch and bound (BB, B&B, or BnB) is a method for solving optimization problems by breaking them down into smaller sub-problems and using a bounding function to eliminate sub-problems that cannot contain the optimal solution.
It is an algorithm ...
algorithms, selected as a citation classic in 1987,
and another influential early paper on
dynamic programming with J. M. Moore.
Lawler was also the first to observe that
matroid intersection can be solved in
polynomial time
In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations p ...
.
The
NP-complete
In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''.
Somewhat more precisely, a problem is NP-complete when:
# It is a decision problem, meaning that for any ...
ness proofs for two of
Karp's 21 NP-complete problems,
directed
Direct may refer to:
Mathematics
* Directed set, in order theory
* Direct limit of (pre), sheaves
* Direct sum of modules, a construction in abstract algebra which combines several vector spaces
Computing
* Direct access (disambiguation), a ...
Hamiltonian cycle
In the mathematics, mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path (graph theory), path in an undirected or directed graph that visits each vertex (graph theory), vertex exactly once. A Hamiltonian cycle (or ...
and
3-dimensional matching, were credited by Karp to Lawler.
The NP-completeness of 3-dimensional matching is an example of one of Lawler's favorite observations, the "mystical power of twoness":
for many combinatorial optimization problems that can be parametrized by an integer, the problem can be solved in
polynomial time
In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations p ...
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 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.
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. 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
Computational biology refers to the use of techniques in computer science, data analysis, mathematical modeling and Computer simulation, computational simulations to understand biological systems and relationships. An intersection of computer sci ...
, including the reconstruction of
evolutionary trees and several works on
sequence alignment
In bioinformatics, a sequence alignment is a way of arranging the sequences of DNA, RNA, or protein to identify regions of similarity that may be a consequence of functional, structural biology, structural, or evolutionary relationships between ...
.
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;
Richard Karp
Richard Manning Karp (born January 3, 1935) is an American computer scientist and computational theorist at the University of California, Berkeley. He is most notable for his research in the theory of algorithms, for which he received a Turin ...
bailed him out.
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".
[.]
Awards and honors
A special issue of the journal ''
Mathematical Programming
Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criteria, from some set of available alternatives. It is generally divided into two subfiel ...
'' (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
The Association for Computing Machinery (ACM) is a US-based international learned society for computing. It was founded in 1947 and is the world's largest scientific and educational computing society. The ACM is a non-profit professional membe ...
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.
References
External links
Lawler in 1977 from the Oberwolfach photo collection
{{DEFAULTSORT:Lawler, Eugene Leighton
1933 births
1994 deaths
American theoretical computer scientists
Harvard University alumni
University of Michigan faculty
University of California, Berkeley faculty
Scientists from the San Francisco Bay Area
Florida State University alumni
20th-century American mathematicians