# Eugene Lawler

Eugene Leighton (Gene) Lawler (né le 28 juillet 1933 à New York et mort le 2 septembre 1994 dans le comté d'Alameda) est un informaticien américain, professeur d'informatique à l'université de Californie à Berkeley$^,$.

## 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 à 1961$^,$. 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 Warnow$^,$.

## 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 contibue à le libérer. Karp rappelle que Lawler est « la conscience sociale de la Division CS, 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 ».

## Livres

* Eugene L. Lawler, Combinatorial optimization: networks and matroids, Holt, Rinehart and Winston, 1976 (ISBN 978-0-03-084866-7) (ISBN 978-0-03-084866-7), republié par Dover Books en 2001, (ISBN 978-0-486-41453-9)) — Lenstra et Shmoys écrivent que ce livre est un classique et qu'il « a contribué à façonner un domaine de recherche émergeant ».
* Eugene L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, et D. Shmoys, Wiley,, The Traveling salesman problem: a guided tour of combinatorial optimization, Wiley, coll. « Wiley-Interscience series in discrete mathematics », 1985 (ISBN 978-0-471-90413-7)
* K. Aardal, J. K. Lenstra, F. Maffioli, et D. Shmoys (éditeurs), Selected publications of Eugene L. Lawler, Centrum voor Wiskunde en Informatica, coll. « CWI tract 126 », 1999 (ISBN 978-90-6196-484-1). Réimpression de 26 articles de recherche.