Eugene Lawler

Eugene Lawler
une illustration sous licence libre serait bienvenue
Biographie
Naissance
Voir et modifier les données sur Wikidata
Décès
Voir et modifier les données sur Wikidata
Nationalité
américaineVoir et modifier les données sur Wikidata
Formation
Activités
Mathématicien, professeur d'université, informaticienVoir et modifier les données sur Wikidata
Autres informations
A travaillé pour
Directeur de thèse
Anthony OettingerVoir et modifier les données sur Wikidata

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

Eugene Leighton (Gene) Lawler (né le 28 juillet 1933 à New York et mort le 2 septembre 1994 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

  • Eugene L. Lawler, Combinatorial optimization: networks and matroids, Holt, Rinehart and Winston, (ISBN 978-0-03-084866-7)[17] (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 »[7].
  • 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 », (ISBN 978-0-471-90413-7)

Références

  • (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Eugene Lawler » (voir la liste des auteurs).
  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 n°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

  • Ressources relatives à la rechercheVoir et modifier les données sur Wikidata :
    • Digital Bibliography & Library Project
    • Mathematics Genealogy Project
  • Notices d'autoritéVoir et modifier les données sur Wikidata :
    • VIAF
    • ISNI
    • IdRef
    • LCCN
    • GND
    • CiNii
    • Pays-Bas
    • Israël
    • NUKAT
    • Australie
    • Norvège
    • Croatie
    • Tchéquie
    • WorldCat
  • icône décorative Portail de l'informatique théorique
  • icône décorative Portail des mathématiques