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 and a professor of computer science at the University of California, Berkeley. [1] [2]
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 applied mathematics in 1962 under the supervision of Anthony G. Oettinger with a dissertation entitled Some Aspects of Discrete Mathematical Programming. [1] [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]
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]
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]
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 and a professor of computer science at the University of California, Berkeley. [1] [2]
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 applied mathematics in 1962 under the supervision of Anthony G. Oettinger with a dissertation entitled Some Aspects of Discrete Mathematical Programming. [1] [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]
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]
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]