Eugene Lawler

Eugene Lawler
une illustration sous licence libre serait bienvenue
Biographie
Naissance
Décès
Nationalité
Formation
Activités
Autres informations
A travaillé pour
Directeur de thèse

modifier - modifier le code - modifier WikidataDocumentation du modèle

Eugene Leighton (Gene) Lawler (né le à New York et mort le dans le comté d'Alameda[1]) est un informaticien américain, professeur d'informatique à l'université de Californie à Berkeley[2],[3].

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[3],[4]. 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[3],[5]. Il est ensuite membre du corps professoral de l'université du Michigan jusqu'en 1971, date à laquelle il déménage pour Berkeley[3]. 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[5],[6].

Recherche

Lawler est un expert en optimisation combinatoire et l'un des fondateurs du domaine[7], 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[2],[8]. 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[9] cité comme un texte "classique" en 1987[3], et un autre article pionnier en programmation dynamique avec J. M. Moore[3],[10]. Lawler a également été le premier à observer que l'intersection des matroïdes peut être calculée en temps polynomial[2],[11]

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é »[2] 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[2] é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[2]. 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[12],[13]. Une autre synthèse ultérieure sur le séquençage est également très citée[14].

À 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[3].

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[15]. 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 »[15].

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[7].

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 »[16].

Livres

Références

  1. ↑ « Eugene Leighton Lawler » sur findagrave.com.
  2. ↑ a b c d e et f Jan Karel Lenstra, « The mystical power of twoness: in memoriam Eugene L. Lawler », Journal of Scheduling, vol. 1, no 1,‎ , p. 3–14 (DOI 10.1002/(SICI)1099-1425(199806)1:1<3::AID-JOS1>3.0.CO;2-B, S2CID 62210683, lire en ligne).
  3. ↑ a b c d e f et g Dan Gusfield, David Shmoys, Jan Karel Lenstra et Tandy Warnow, « In Memoriam Eugene L. Lawler », Journal of Computational Biology, vol. 1, no 4,‎ , p. 255–256 (DOI 10.1089/cmb.1994.1.255). Réimprimé dans « In memoriam Eugene L. Lawler », SIGACT News, vol. 25, no 4,‎ , p. 108–109 (DOI 10.1145/190616.190626 Accès libre, S2CID 5267081).
  4. ↑ Comité de rédaction (1995) In Memoriam: Eugene L. Lawler, SIAM Journal on Computing vol 24 no 1, 1-2.
  5. ↑ a et b (en) « Eugene L. Lawler », sur le site du Mathematics Genealogy Project.
  6. ↑ Theoretical computer science academic genealogy, Ian Parberry, 1996, retrieved 2010-09-17.
  7. ↑ a b et c Jan Karel Lenstra et David Schmoys, « Preface », Mathematical Programming, vol. 82, nos 1–2,‎ , p. 1 (DOI 10.1007/BF01585862).
  8. ↑ Malcolm W. Browne, « A Soviet discovery rocks world of mathematics: Russian's surprise problem-solving discovery reported », The New York Times,‎ .
  9. ↑ E. L. Lawler et D. E. Wood, « Branch-and-bound methods: A survey », Operations Research, vol. 14, no 4,‎ , p. 699–719 (DOI 10.1287/opre.14.4.699, JSTOR 168733).
  10. ↑ E. L. Lawler et J. M. Moore, « A functional equation and its application to resource allocation and sequencing problems », Management Science, vol. 16, no 1,‎ , p. 77–84 (DOI 10.1287/mnsc.16.1.77, JSTOR 2628367).
  11. ↑ E. L. Lawler, « Matroid intersection algorithms », Mathematical Programming, vol. 9, no 1,‎ , p. 31–56 (DOI 10.1007/BF01681329, S2CID 206801650).
  12. ↑ Ronald L. Graham, Eugene L. Lawler, Jan K. Lenstra et A. H. G. Rinnooy Kan, « Optimization and approximation in deterministic sequencing and scheduling: a survey », dans Discrete optimization I: proceedings of the Advanced research institute on discrete optimization and systems applications, North-Holland, coll. « Annals of Discrete Mathematics » (no 4), , p. 287.
  13. ↑ Vincent T'kindt et Jean-Charles Billaut, Multicriteria scheduling: theory, models and algorithms, Springer-Verlag, (ISBN 978-3-540-43617-1).
  14. ↑ Eugene L. Lawler, Jan K. Lenstra, A. H. G. Rinnooy Kan et David B. Shmoys, « Sequencing and scheduling: algorithms and complexity », dans S. C. Graves, Alexander Rinnooy Kan et Zipkin Paul Herbert Zipkin (éditeurs), Logistics of Production and Inventory, North Holland, coll. « Handbooks in Operations Research and Management Science » (no 4), , 445–522 p..
  15. ↑ a et b Richard Karp, « A Personal View of Computer Science at Berkeley », EECS Department, University of California, Berkeley,‎ (lire en ligne).
  16. ↑ Eugene L. Lawler Award, ACM, retrieved 2010-09-14.
  17. ↑ Bellman, R. E., « Review: Combinatioral optimization: networks and matroids, by Eugene L. Lawler », Bull. Amer. Math. Soc., vol. 84, no 3,‎ , p. 461–463 (DOI 10.1090/s0002-9904-1978-14493-0 Accès libre, lire en ligne)

Liens externes