David P. Williamson

Biographie

Naissance	2 avril 1967 (56 ans)
Nationalité	américaine
Formation	Massachusetts Institute of Technology
Activités	Mathématicien, informaticien

Autres informations

A travaillé pour	Université Cornell
Membre de	Society for Industrial and Applied Mathematics (2016)
Directeur de thèse	Michel Goemans
Distinctions	Liste détaillée Prix Fulkerson (2000) Prix Frederick W. Lanchester (2013) Membre honoraire de la Society for Industrial and Applied Mathematics (2016) Prix Leroy P. ​​Steele pour contribution fondamentale à la recherche (2022) ACM Fellow

modifier - modifier le code - modifier Wikidata

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

• 1994 : Prix A.-W.-Tucker^[7]
• 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^[8]
• 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