Eugene Lawler
![une illustration sous licence libre serait bienvenue](http://upload.wikimedia.org/wikipedia/commons/thumb/f/f7/Defaut_2.svg/langfr-260px-Defaut_2.svg.png)
Naissance | ![]() |
---|---|
Décès | ![]() |
Nationalité | américaine ![]() |
Formation | |
Activités | Mathématicien, professeur d'université, informaticien ![]() |
A travaillé pour | |
---|---|
Directeur de thèse | Anthony Oettinger ![]() |
modifier - modifier le code - modifier Wikidata
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)
- 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 », (ISBN 978-90-6196-484-1). Réimpression de 26 articles de recherche.
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).
- ↑ « Eugene Leighton Lawler » sur findagrave.com.
- ↑ 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).
- ↑ 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
, S2CID 5267081).
- ↑ Comité de rédaction (1995) In Memoriam: Eugene L. Lawler, SIAM Journal on Computing vol 24 n°1, 1-2.
- ↑ a et b (en) « Eugene L. Lawler », sur le site du Mathematics Genealogy Project.
- ↑ Theoretical computer science academic genealogy, Ian Parberry, 1996, retrieved 2010-09-17.
- ↑ a b et c Jan Karel Lenstra et David Schmoys, « Preface », Mathematical Programming, vol. 82, nos 1–2, , p. 1 (DOI 10.1007/BF01585862).
- ↑ Malcolm W. Browne, « A Soviet discovery rocks world of mathematics: Russian's surprise problem-solving discovery reported », The New York Times, .
- ↑ 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).
- ↑ 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).
- ↑ E. L. Lawler, « Matroid intersection algorithms », Mathematical Programming, vol. 9, no 1, , p. 31–56 (DOI 10.1007/BF01681329, S2CID 206801650).
- ↑ 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.
- ↑ Vincent T'kindt et Jean-Charles Billaut, Multicriteria scheduling: theory, models and algorithms, Springer-Verlag, (ISBN 978-3-540-43617-1).
- ↑ 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..
- ↑ a et b Richard Karp, « A Personal View of Computer Science at Berkeley », EECS Department, University of California, Berkeley, (lire en ligne).
- ↑ Eugene L. Lawler Award, ACM, retrieved 2010-09-14.
- ↑ 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
, lire en ligne)
Liens externes
- Ressources relatives à la recherche
:
- Digital Bibliography & Library Project
- Mathematics Genealogy Project
- Notices d'autorité
:
- VIAF
- ISNI
- IdRef
- LCCN
- GND
- CiNii
- Pays-Bas
- Israël
- NUKAT
- Australie
- Norvège
- Croatie
- Tchéquie
- WorldCat
Portail de l'informatique théorique
Portail des mathématiques