Eugene Leighton (Gene) Lawler (1933 – 2 de septiembre de 1994) fue un científico 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 de tres años en matemáticas en la Universidad Estatal de Florida . Recibió una maestría en 1957, [2] e hizo 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, Huzur Saran, David Shmoys y Tandy Warnow . [5] [7]
Lawler fue un experto en optimización combinatoria y uno de los fundadores del campo, [8] autor del ampliamente utilizado libro de texto Combinatorial Optimization: Networks and Matroids y coautor de The Traveling Salesman Problem: a guided tour of combinatorial optimized . Jugó un papel central en rescatar el método elipsoide para 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 ramificación y acotación , [10] seleccionada como un clásico de citación en 1987, [2] y otro influyente artículo temprano sobre programación dinámica con JM Moore. [2] [11] Lawler también fue el primero en observar que la intersección de matroides se puede resolver en tiempo polinomial . [1] [12]
Las pruebas de NP-completitud para dos de los 21 problemas NP-completos de Karp , el ciclo hamiltoniano dirigido y el emparejamiento tridimensional , fueron acreditadas por Karp a Lawler. [1] La NP-completitud del emparejamiento tridimensional es un ejemplo de una de las observaciones favoritas de Lawler, el "poder místico de la dualidad": [1] para muchos problemas de optimización combinatoria que pueden parametrizarse con un entero, el problema puede resolverse en tiempo polinomial cuando el parámetro es dos, pero se vuelve NP-completo cuando el parámetro es tres. Para el emparejamiento tridimensional, la versión solucionable del problema con 2 parámetros es el emparejamiento de grafos ; el mismo fenómeno surge en las complejidades de la coloración 2 y 3 para grafos, en el problema de la 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 por eso se había 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 talleres de trabajo . [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] Otro estudio posterior también es muy citado (más de 1000 citas cada uno en Google Scholar). [15]
A finales de la década de 1980, Lawler cambió el enfoque de su investigación a 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 estaba de año sabático en Berkeley, Lawler participó en una protesta contra la guerra de Vietnam que condujo a la detención de 483 manifestantes, incluido Lawler; [3] Richard Karp lo rescató. [6] Karp recuerda a Lawler como "la conciencia social de la División de Ciencias de la Computación, siempre pendiente del bienestar de los estudiantes y especialmente preocupado 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. [8]
El premio Eugene L. Lawler de la ACM es otorgado por la Association for Computing Machinery cada dos años por "contribuciones humanitarias en el campo de la informática y la ciencia de la computación". [16]