Eugene Leighton (Gene) Lawler (1933 - 2 de septiembre de 1994) fue un informático estadounidense y profesor de informática en la Universidad de California, Berkeley . [1] [2]
Lawler llegó a Harvard como estudiante de posgrado en 1954, después de un programa de licenciatura en matemáticas de tres años en la Universidad Estatal de Florida . Recibió una maestría en 1957, [2] y tomó una pausa en sus estudios, durante la cual fue brevemente a la facultad de derecho y trabajó en el ejército de los EE. UU., en una empresa de muelas abrasivas, [3] y como ingeniero eléctrico en Sylvania. de 1959 a 1961. [2] [4] Regresó a Harvard en 1958 y completó su doctorado. en matemáticas aplicadas en 1962 bajo la supervisión de Anthony G. Oettinger con una disertación titulada Algunos aspectos de la programación matemática discreta . [1] [2] [5] Luego se convirtió en miembro de la facultad de la Universidad de Michigan hasta 1971, cuando se mudó a Berkeley. [2] Se jubiló en 1994, poco antes de su muerte. [6]
En Berkeley, los estudiantes de doctorado de Lawler incluyeron a Marshall Bern, Chip Martel , Arvind Raghunathan, Arnie Rosenthal, Hazur Saran, David Shmoys y Tandy Warnow . [5] [7]
Lawler era un experto en optimización combinatoria y fundador del campo, [8] autor del libro de texto ampliamente utilizado Combinatorial Optimization: Networks and Matroids y coautor de The Travelling Salesman Problem: a guiado tour of combinatorial optimización . Desempeñó un papel central en el rescate del método elipsoide para la programación lineal de la oscuridad en Occidente. [1] [9] También escribió (con DE Wood) una encuesta de 1966 muy citada sobre algoritmos de rama y enlace , [10] seleccionada como un clásico de citas en 1987, [2] y otro artículo temprano influyente sobre programación dinámica con JM Moore . [2] [11] Lawler también fue el primero en observar que la intersección matroide se puede resolver en tiempo polinomial . [1] [12]
Karp atribuyó a Lawler las pruebas de completitud NP para dos de los 21 problemas NP-completos de Karp , el ciclo hamiltoniano dirigido y el emparejamiento tridimensional . [1] La completitud NP del emparejamiento tridimensional es un ejemplo de una de las observaciones favoritas de Lawler, el "poder místico de la duplicidad": [1] para muchos problemas de optimización combinatoria que pueden parametrizarse mediante un número entero, el problema puede ser se resuelve en tiempo polinómico cuando el parámetro es dos, pero se vuelve NP-completo cuando el parámetro es tres. Para la comparación tridimensional, la versión del problema con parámetro 2 que se puede resolver es la comparación de gráficos ; El mismo fenómeno surge en las complejidades de 2 colores y 3 colores para gráficos, en el problema de intersección de matroides para intersecciones de dos o tres matroides, y en 2-SAT y 3-SAT para problemas de satisfacibilidad . Lenstra [1] escribe que "Gene invariablemente comentaba que es por eso que se ha ideado un mundo con dos sexos".
Durante la década de 1970, Lawler hizo grandes avances en la sistematización de algoritmos para la programación de trabajos . [1] Su estudio de 1979 sobre el tema introdujo la notación de tres campos para problemas de programación teórica , que (a pesar de la existencia de notaciones anteriores) se convirtió en estándar en el estudio de algoritmos de programación. [13] [14] Otra encuesta posterior también es muy citada (más de 1000 citas cada una en Google Scholar). [15]
A finales de la década de 1980, Lawler centró su investigación en problemas de biología computacional , incluida la reconstrucción de árboles evolutivos y varios trabajos sobre alineación de secuencias . [2]
En la primavera de 1969, mientras se tomaba un año sabático en Berkeley, Lawler participó en una protesta contra la guerra de Vietnam que condujo al arresto de 483 manifestantes, incluido Lawler; [3] Richard Karp lo sacó bajo fianza. [6] Karp recuerda a Lawler como "la conciencia social de la División CS, siempre velando por el bienestar de los estudiantes y especialmente preocupada por las mujeres, las minorías y los estudiantes discapacitados". [6]
En 1998 se dedicó un número especial de la revista Mathematical Programming (vol. 82, números 1 y 2) en honor a Lawler.
El premio ACM Eugene L. Lawler lo otorga la Association for Computing Machinery cada dos años por "contribuciones humanitarias en la informática y la informática". [dieciséis]