Eugene Lawler
Encyclopedia
Eugene Leighton Lawler (1933 – September 2, 1994) was an American computer scientist
, a professor of computer science at the University of California, Berkeley
.
as a graduate student in 1954, after a three-year undergraduate program at a southern university. He received a masters 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 Electric Products. He returned to Harvard in 1958, and completed his Ph.D. in 1962 under the supervision of Anthony G. Oettinger. He then became a faculty member at the University of Michigan
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.
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
for linear programming from obscurity in the West. He also wrote (with D. E. Wood) a heavily-cited 1966 survey on branch and bound
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.
The NP-complete
ness proofs for two of Karp's 21 NP-complete problems
, directed
Hamiltonian cycle 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 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
, including the reconstruction of evolutionary trees and several works on sequence alignment
.
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".
(vol. 82, issues 1–2) was dedicated in Lawler's honor in 1998.
The Eugene L. Lawler Award is given by the Association of Computing Machinery every two years for "humanitarian contributions within computer science and informatics".
Computer scientist
A computer scientist is a scientist who has acquired knowledge of computer science, the study of the theoretical foundations of information and computation and their application in computer systems....
, a professor of computer science at the University of California, Berkeley
University of California, Berkeley
The University of California, Berkeley , is a teaching and research university established in 1868 and located in Berkeley, California, USA...
.
Academic life
Lawler came to Harvard UniversityHarvard University
Harvard University is a private Ivy League university located in Cambridge, Massachusetts, United States, established in 1636 by the Massachusetts legislature. Harvard is the oldest institution of higher learning in the United States and the first corporation chartered in the country...
as a graduate student in 1954, after a three-year undergraduate program at a southern university. He received a masters 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 Electric Products. He returned to Harvard in 1958, and completed his Ph.D. in 1962 under the supervision of Anthony G. Oettinger. He then became a faculty member at the University of Michigan
University of Michigan
The University of Michigan is a public research university located in Ann Arbor, Michigan in the United States. It is the state's oldest university and the flagship campus of the University of Michigan...
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
Arvind Raghunathan
Arvind Raghunathan is the CEO of Roc Capital Management LP . On February 25, 2009, it was announced that Raghunathan and his associates would be leaving Deutsche Bank to set up the independent quant trading hedge fund.Raghunathan was the former Managing Director and Head of Global Arbitrage at...
, Arnie Rosenthal, Huzur Saran, David Shmoys
David Shmoys
David Shmoys is currently a Professor in both the School of Operations Research and Information Engineering and the Department of Computer Science at Cornell University. He obtained his Ph.D. from the University of California, Berkeley in 1984...
, and Tandy Warnow.
Research
Lawler was an expert on combinatorial optimizationCombinatorial optimization
In applied mathematics and theoretical computer science, combinatorial optimization is a topic that consists of finding an optimal object from a finite set of objects. In many such problems, exhaustive search is not feasible...
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
Ellipsoid method
In mathematical optimization, the ellipsoid method is an iterative method for minimizing convex functions. When specialized to solving feasible linear optimization problems with rational data, the ellipsoid method is an algorithm, which finds an optimal solution in a finite number of steps.The...
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
Branch and bound is a general algorithm for finding optimal solutions of various optimization problems, especially in discrete and combinatorial optimization...
algorithms, selected as a citation classic in 1987,
and another influential early paper on dynamic programming
Dynamic programming
In mathematics and computer science, dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems exhibiting the properties of overlapping subproblems which are only slightly smaller and optimal substructure...
with J. M. Moore. Lawler was also the first to observe that matroid intersection
Matroid intersection
In combinatorial optimization, the matroid intersection problem is to find a largest common independent set in two matroids over the same ground set. If the elements of the matroid are assigned real weights, the weighted matroid intersection problem is to find a common independent set with the...
can be solved in polynomial time.
The NP-complete
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
ness proofs for two of Karp's 21 NP-complete problems
Karp's 21 NP-complete problems
One of the most important results in computational complexity theory was Stephen Cook's 1971 demonstration of the first NP-complete problem, the boolean satisfiability problem...
, directed
Directed graph
A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
Hamiltonian cycle and 3-dimensional matching
3-dimensional matching
In the mathematical discipline of graph theory, a 3-dimensional matching is a generalization of bipartite matching to 3-uniform hypergraphs...
, 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 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
Bipartite graph
In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...
and 3-coloring
Graph coloring
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the...
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
Jan Karel Lenstra
Jan Karel Lenstra is a Dutch mathematician and operations researcher, known for his work on scheduling algorithms, local search, and the travelling salesman problem....
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
Job Shop Scheduling
Job shop scheduling is an optimization problem in computer science in which ideal jobs are assigned to resources at particular times. The most basic version is as follows:...
. His 1979 survey on the subject introduced the three-field notation for theoretic scheduling problems
Notation for theoretic scheduling problems
A convenient notation for theoretic scheduling problems was introduced by Ronald Graham, Eugene Lawler, Jan Karel Lenstra and Alexander Rinnooy Kan. It consists of three fields: α, β and γ.Each field may be a comma separated list of words...
, 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
Computational biology involves the development and application of data-analytical and theoretical methods, mathematical modeling and computational simulation techniques to the study of biological, behavioral, and social systems...
, including the reconstruction of evolutionary trees and several works on sequence alignment
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, or evolutionary relationships between the sequences. Aligned sequences of nucleotide or amino acid residues are...
.
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 KarpRichard Karp
Richard Manning Karp is a computer scientist and computational theorist at the University of California, Berkeley, notable for research in the theory of algorithms, for which he received a Turing Award in 1985, The Benjamin Franklin Medal in Computer and Cognitive Science in 2004, and the Kyoto...
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 ProgrammingMathematical Programming
Mathematical Programming, established in 1971, and published by Springer Science+Business Media, is the official scientific journal of the Mathematical Optimization Society. It currently consists of two series: A and B. The "A" series contains general publications. The "B" series focuses on topical...
(vol. 82, issues 1–2) was dedicated in Lawler's honor in 1998.
The Eugene L. Lawler Award is given by the Association of Computing Machinery every two years for "humanitarian contributions within computer science and informatics".
Books
- Combinatorial Optimization: Networks and Matroids (Holt, Rinehart, and Winston 1976, ISBN 9780030848667, republished by Dover Books in 2001, ISBN 9780486414539). 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. LenstraJan Karel LenstraJan Karel Lenstra is a Dutch mathematician and operations researcher, known for his work on scheduling algorithms, local search, and the travelling salesman problem....
, A. H. G. Rinnooy KanAlexander Rinnooy KanAlexander Hendrik George Rinnooy Kan is a Dutch mathematician and business leader. The Dutch newspaper de Volkskrant named him the most influential man in the Netherlands in 2007, 2008 and 2009....
, and D. Shmoys, Wiley, 1985, ISBN 9780471904137). - Selected publications of Eugene L. Lawler (K. Aardal, J. K. Lenstra, F. Maffioli, and D. ShmoysDavid ShmoysDavid Shmoys is currently a Professor in both the School of Operations Research and Information Engineering and the Department of Computer Science at Cornell University. He obtained his Ph.D. from the University of California, Berkeley in 1984...
, eds., CWI Tracts 126, Centrum Wiskunde & Informatica, 1999, ISBN 9789061964841). Reprints of 26 of Lawler's research papers.
External links
- Lawler in 1977, from the Oberwolfach photo collection