Share to: share facebook share twitter share wa share telegram print page

David P. Williamson

Page d’aide sur l’homonymie

Pour les articles homonymes, voir Williamson.

David P. Williamson
Biographie
Naissance
Voir et modifier les données sur Wikidata (57 ans)
Nationalité
Formation
Activités
Autres informations
A travaillé pour
Membre de
Directeur de thèse
Distinctions

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

David Paul Williamson (né en 1967) est un mathématicien américain, professeur de recherche opérationnelle à l'université Cornell[1] et rédacteur en chef du SIAM Journal on Discrete Mathematics [2].

Formation et carrière

Il obtient son doctorat en 1993 du Massachusetts Institute of Technology sous la direction de Michel Goemans, avec une thèse intitulée « On the design of approximation algorithms for a class of graph problems »[3]. Il travaille comme post-doctorant auprès d'Éva Tardos à l'université Cornell puis au IBM Thomas J. Watson Research Center. De 2000 à 2003 il est Senior Manager du Computer Science Principles and Methodologies Group au Almaden Research Center d'IBM. Depuis 2004 il est professeur à l'université Cornell.

Travaux

Il est surtout connu pour ses travaux avec Goemans sur les algorithmes d'approximation basés sur la programmation semi-définie (notamment pour le problème de la coupe maximum)[4], pour lesquels ils ont remporté le prix Fulkerson en 2000[5]. Il a également reçu le prix Frederick W. Lanchester en 2013, conjointement avec David Shmoys. En 2022, il a reçu le prix Leroy P. Steele pour sa contribution séminale à la recherche, avec Michel Goemans, pour leur article "Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming," (publié en 1995 dans le Journal of the ACM)[6].

Prix et distinctions

Publications

  • avec David Shmoys: The Design of Approximation Algorithms, Cambridge University Press 2011.
  • avec Guolong Lin, Chandrashekhar Nagarajan, Rajmohan Rajaraman: A General Approach for Incremental Approximation and Hierarchical Clustering, SIAM Journal on Computing, vol 39, 2010, pp. 3633–3669.
  • avec Mateo Restrepo: A Simple GAP-Canceling Algorithm for the Generalized Maximum Flow Problem, Mathematical Programming, vol 118, 2009, pp. 47–74.
  • avec Anke van Zuylen Deterministic Pivoting Algorithms for Constrained Ranking and Clustering Problems, Mathematics of Operations Research, vol 34, 2009, pp. 594–620.
  • avec Yogeshwer Sharma: Stackelberg Thresholds in Network Routing Games or the Value of Altruism, Games and Economic Behavior, vol 67, 2009, pp. 174–190.
  • avec Goemans: Improved approximation algorithms for the maximum cut and satisfiability problems using semi-definite programming, Journal of the ACM, vol 42, 1995, pp. 1115–1145.

Références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « David P. Williamson » (voir la liste des auteurs).
  1. ↑ Faculty profile, Cornell University, retrieved 2015-06-07.
  2. ↑ « web site », sur SIAM Journal on Discrete Mathematics (consulté le ).
  3. ↑ (en) « David P. Williamson », sur le site du Mathematics Genealogy Project
  4. ↑ Michel X. Goemans et David P. Williamson, « Improved approximation algorithms for the maximum cut and satisfiability problems using semi-definite programming », Journal of the ACM, vol. 42, no 6,‎ , p. 1115–1145.
  5. ↑ (en) « 2000 Fulkerson Prize », Notices of the American Mathematical Society, vol. 47, no 9,‎ , p. 1086 (lire en ligne).
  6. ↑ AMS Steele Prize for Seminal Contribution to Research 2022
  7. ↑ (en) « Mathematical Optimization Society », sur mathopt.org (consulté le )
  8. ↑ « Frederick W. Lanchester Prize - INFORMS », sur informs.org (consulté le )

Liens externes
Kembali kehalaman sebelumnya