Le prix Fulkerson est remis conjointement par la Mathematical Programming Society (MPS) et l'American Mathematical Society (AMS) afin de récompenser les articles remarquables parus dans la presse scientifique, dans le domaine des mathématiques discrètes.
Trois prix de US sont remis lors du symposium international de l'AMS (tous les trois ans). À l'origine, le prix venait de donations des « amis de Delbert Ray Fulkerson », administrées par l'AMS. Désormais, les prix viennent de donations administrées par la MPS.
Lauréats
1979 : Richard M. Karp, pour sa classification de nombreux problèmes NP-complets, Paul Seymour, pour sa généralisation du théorème flot-max/coupe-min aux matroïdes, Kenneth Appel et Wolfgang Haken pour le théorème des quatre couleurs. 1982 : et Arkadi Nemirovski, Leonid Khatchian, Martin Grötschel, László Lovász et Alexander Schrijver, pour la méthode de l'ellipsoïde en optimisation linéaire. et D. I. Falikman pour leur preuve de la conjecture de van der Waerden d'après laquelle la matrice dont toutes les entrées sont égales est celle dont le permanent est minimal parmi les matrice bistochastique. 1985 : pour les bornes exactes sur la des progressions arithmétiques, Hendrik Lenstra, pour l'utilisation de la géométrie des nombres pour les problèmes d'optimisation linéaire en nombres entiers, pour un algorithme polynomial de résolution du problème de l'isomorphisme de graphes dans le cas des graphes de degrés bornés. 1988 : Éva Tardos, pour son algorithme qui résout le en temps polynomial fort, Narendra Karmarkar, pour son algorithme polynomial pour l'optimisation linéaire. 1991 : Martin Dyer, Alan M. Frieze et Ravindran Kannan, pour leur utilisation de marches aléatoires pour des algorithmes d'approximation d'estimation de certains volumes. Alfred Lehman, pour les analogues, dans les matrices binaires, de la théorie des graphes parfaits, Nikolai E. Mnev, pour ce qui est appelé le et qui statue que tout ensemble semi-algébrique est équivalent à l'espace des réalisations d'un matroïde orienté. 1994 : Louis Billera, pour avoir trouvé des bases des espaces de fonctions polynomiales par morceau sur des triangulations de l'espace, Gil Kalai, pour les progrès dans la conjecture de Hirsch, Neil Robertson et Paul Seymour et Robin Thomas, pour le cas à 6 couleurs de la conjecture de Hadwiger. 1997 : , pour ses travaux sur les nombres de Ramsey. 2000 : Michel Goemans et David P. Williamson, pour des algorithmes d'approximation basés sur l'optimisation semi-définie positive (notamment pour le problème de la coupe maximum), Michele Conforti, Gérard Cornuéjols et , pour la décomposition des . 2003 : Jim Geelen, A. M. H. Gerards et A. Kapoor, pour des avancées sur la à propos des , Bertrand Guenin, pour sa caractérisation par mineurs des graphes faiblement bipartis, Satoru Iwata, Lisa Fleischer et Satoru Fujishige, Alexander Schrijver, pour avoir montré que la minimisation d'une fonction sous-modulaire peut être faite en temps fortement polynomial. 2006 : Manindra Agrawal, Neeraj Kayal et Nitin Saxena pour le test de primalité AKS ; Mark Jerrum, Alistair Sinclair et Eric Vigoda pour l'approximation du permanent ; Neil Robertson et Paul Seymour pour la résolution de la conjecture de Wagner (maintenant connue sous le nom de théorème de Robertson-Seymour). 2009 : Maria Chudnovsky, Neil Robertson, Paul Seymour, et Robin Thomas pour leur preuve du théorème fort des graphes parfaits. Daniel Spielman et Shang-Hua Teng pour leurs travaux sur l'analyse lisse d'algorithme (smoothed analysis). Thomas Hales et Samuel P. Ferguson, pour leur démonstration de la conjecture de Kepler. 2012 : Sanjeev Arora, et Umesh Vazirani pour leur amélioration de la complexité des algorithmes d'approximation pour calculer les séparateurs de graphe (de O() à O()) et leurs progrès sur des problèmes liés; Anders Johansson, Jeff Kahn et Van H. Vu pour leur détermination du seuil de densité d'arêtes au-delà duquel un graphe aléatoire est toujours réunion de copies disjointes d'un graphe donné plus petit ; László Lovász et Balázs Szegedy pour leur caractérisation de la multiplicité d'un sous-graphe dans une suite de graphes denses. 2015 : pour son contre-exemple de la conjecture de Hirsch.. 2018 : Robert Morris, Yoshiharu Kohayakawa, Simon Griffiths, Peter Allen, et Julia Böttcher pour The chromatic thresholds of graphs pour The Matching Polytope has Exponential Extension Complexity 2021 : Béla Csaba, Daniela Kühn, Allan Lo, Deryk Osthus et Andrew Treglown pour Proof of the 1-factorization and Hamilton decomposition conjectures Jin-Yi Cai et Xi Chen pour Complexity of Counting CSP with Complex Weights Ken-Ichi Kawarabayashi et pour Deterministic Edge Connectivity in Near-Linear Time 2024 : Ben Cousins et Santosh Vempala pour Le refroidissement gaussien et les algorithmes O*(n^3) pour le volume et le volume gaussienne, SIAM Journal on Computing Nathan Keller et Noam Lifshitz pour La méthode Junta pour les hypergraphes et la conjecture simplexe d’Erdos-Chvátal, Advances in Mathematics Zilin Jiang, Jonathan Tidor, Yuan Yao, Shengtong Zhang et Yufei Zhao pour Les lignes équiangulaires à angle fixe, Annals of Mathematics
Notes et références
Lien externe sur le site de l'AMS, avec détails sur le prix.
Catégorie:Distinction en mathématiques Catégorie:Distinction de l'American Mathematical Society