Eugene Leighton (Gene) Lawler (né le à New York et mort le dans le comté d'Alameda« Eugene Leighton Lawler » sur findagrave.com.) est un informaticien américain, professeur d'informatique à l'université de Californie à Berkeley.. Réimprimé dans ..
Carrière académique Lawler obtient une licence en mathématiques en trois ans à l'université d'État de Floride et en 1954 arrive à l'université Harvard en 1954. Il obtient une maîtrise en 1957 puis passe brièvement à la faculté de droit et travaille dans l'armée américaine, dans une entreprise de pneumatiques, et comme ingénieur électricien dans l'entreprise Sylvania de 1959 à 1961Comité de rédaction (1995) In Memoriam: Eugene L. Lawler, SIAM Journal on Computing vol 24 , 1-2.. Il retourne à Harvard en 1958 et obtient son doctorat en mathématiques appliquées en 1962 sous la direction d'Anthony Oettinger avec une thèse intitulée Some Aspects of Discrete Mathematical Programming.. Il est ensuite membre du corps professoral de l'université du Michigan jusqu'en 1971, date à laquelle il déménage pour Berkeley. Il prend sa retraite en 1994, peu avant sa mort.
Les doctorants de Lawler à Berkeley comprennent Marshall Bern, Chip Martel, Arvind Raghunathan, Arnie Rosenthal, Huzur Saran, David Shmoys et Tandy WarnowTheoretical computer science academic genealogy, Ian Parberry, 1996, retrieved 2010-09-17..
Recherche Lawler est un expert en optimisation combinatoire et l'un des fondateurs du domaine, auteur du manuel Combinatorial Optimization: Networks and Matroids et co-auteur de The Travelling Salesman Problem: A Guided Tour of Combinatorial Optimisation. Il a joué un rôle central dans la divulgation — en occident — de la méthode de l'ellipsoïde en programmation linéaire.. Il a également écrit en 1966 (avec D. E. Wood) un article de synthèse très cité sur les algorithmes de séparation et évaluation. cité comme un texte "classique" en 1987, et un autre article pionnier en programmation dynamique avec J. M. Moore.. Lawler a également été le premier à observer que l'intersection des matroïdes peut être calculée en temps polynomial.
Les preuves de NP-complétude pour deux des 21 problèmes NP-complets de Karp, à savoir la chaîne hamiltonienne dirigée et l'appariement à 3 dimensions, ont été attribuées par Karp à Lawler. La NP-complétude de l'appariement tridimensionnel est un exemple de l'une des observations préférées de Lawler sur le « pouvoir mystique de la dualité » pour de nombreux problèmes d'optimisation combinatoire qui peuvent être paramétrés par un nombre entier : le problème peut être résolu en temps polynômial quand le paramètre vaut 2 mais devient NP-complet lorsque le paramètre est égal à 3. Pour l'appariement tridimensionnel, la version résoluble du problème en paramètre 2 est le couplage ; le même phénomène se produit dans les complexités de la 2-coloration et de la 3-coloration pour les graphes, dans le problème d'intersection des matroïdes pour les intersections de deux ou trois matroïdes, et dans 2-SAT et 3-SAT pour le problème de satisfaisabilité. Lenstra écrit que « Gene commenterait invariablement que c'est pour cela qu'un monde à deux sexes a été conçu ».
Au cours des années 1970, Lawler a fait de grands progrès dans la systématisation des algorithmes de séquençage de tâches. Son article de synthèse de 1979 sur le sujet a introduit la notation à trois champs pour les problèmes théoriques d'ordonnancement, qui (malgré l'existence de notations antérieures) est devenue la norme dans l'étude des algorithmes d'ordonnancement... Une autre synthèse ultérieure sur le séquençage est également très citée..
À la fin des années 1980, Lawler oriente ses recherches vers les problèmes de biologie computationnelle, notamment la reconstruction des arbres évolutifs et plusieurs travaux sur l'alignement de séquences.
Activisme politique Au printemps 1969, alors qu'il est en congé sabbatique à Berkeley, Lawler participe à une manifestation contre la guerre du Vietnam qui conduit à l'arrestation de 483 manifestants, dont Lawler ; Richard Karp contribue à le libérer. Karp rappelle que Lawler est « la conscience sociale de la Division , toujours à la recherche du bien-être des étudiants et particulièrement soucieux du sort des femmes, des minorités et des étudiants handicapés »..
Récompenses et honneurs Un numéro spécial de la revue Mathematical Programming (vol. 82, numéros 1–2) est consacré à honorer Lawler en 1998..
Le prix ACM Eugene L. Lawler est décerné tous les deux ans par l'Association for Computing Machinery pour « contributions humanitaires dans le domaine de l'informatique et de l'informatique »Eugene L. Lawler Award, ACM, retrieved 2010-09-14..
Livres , republié par Dover Books en 2001, ) — Lenstra et Shmoys écrivent que ce livre est un classique et qu'il « a contribué à façonner un domaine de recherche émergeant ».
. Réimpression de 26 articles de recherche.
Références
Liens externes
Catégorie:Mathématicien américain du XXe siècle Catégorie:Étudiant de l'université d'État de Floride Catégorie:Professeur à l'université de Californie à Berkeley Catégorie:Professeur à l'université du Michigan Catégorie:Étudiant de l'université Harvard Catégorie:Décès en septembre 1994 Catégorie:Naissance en juillet 1933 Catégorie:Décès à 61 ans