David Paul Williamson (né en 1967) est un mathématicien américain, professeur de recherche opérationnelle à l'université CornellFaculty profile, Cornell University, retrieved 2015-06-07. et rédacteur en chef du SIAM Journal on Discrete Mathematics ..
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 « ». 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)., pour lesquels ils ont remporté le prix Fulkerson en 2000.. 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)AMS Steele Prize for Seminal Contribution to Research 2022.
Prix et distinctions 1994 : Prix A.-W.-Tucker 1996 : Prix DiPrima 1999 : Prix SIAM Group of Optimization 2000 : Prix Fulkerson (avec Michel Goemans) 2010 : Prix de recherche Humboldt 2013 : Prix Frederick W. Lanchester Depuis 2013 : Membre de l'Association for Computing Machinery 2022 : Prix Leroy P. Steele
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
Liens externes
Page personnelle
Catégorie:Professeur à l'université Cornell Catégorie:Mathématicien américain du XXIe siècle Catégorie:Mathématicien américain du XXe siècle Catégorie:Lauréat du prix Leroy P. Steele Catégorie:Lauréat du prix Lanchester Catégorie:Lauréat du prix Fulkerson Catégorie:Naissance en avril 1967