Prix Fulkerson

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 1 500 dollars 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

Une catégorie est consacrée à ce sujet : Lauréat du prix Fulkerson.

• 1979 :
  • Richard M. Karp, pour sa classification de nombreux problèmes NP-complets^[1],
  • Paul Seymour, pour sa généralisation du théorème flot-max/coupe-min aux matroïdes^[2],
  • Kenneth Appel et Wolfgang Haken pour le théorème des quatre couleurs^[3].
• 1982 :
  • David B. Youdine (de) 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^{[4],[5],[6],[7]}.
  • Georgy Egorychev (en) 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^[8],[9].
• 1985 :
  • Jozsef Beck (en) pour les bornes exactes sur la discrépance (en) des progressions arithmétiques ^[10],
  • Hendrik Lenstra, pour l'utilisation de la géométrie des nombres pour les problèmes d'optimisation linéaire en nombres entiers^[11],
  • Eugene M. Luks (en) 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^[12],[13].
• 1988 :
  • Éva Tardos, pour son algorithme qui résout le problème de circulation (en) en temps polynomial fort^[14],
  • Narendra Karmarkar, pour son algorithme polynomial pour l'optimisation linéaire^[15].
• 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^[16].
  • Alfred Lehman, pour les analogues, dans les matrices binaires, de la théorie des graphes parfaits^[17],
  • Nikolai E. Mnev, pour ce qui est appelé le théorème d'universalité de Mnev (en) et qui statue que tout ensemble semi-algébrique est équivalent à l'espace des réalisations d'un matroïde orienté^[18].
• 1994 :
  • Louis Billera, pour avoir trouvé des bases des espaces de fonctions polynomiales par morceau sur des triangulations de l'espace^[19],
  • Gil Kalai, pour les progrès dans la conjecture de Hirsch^[20],
  • Neil Robertson et Paul Seymour et Robin Thomas, pour le cas à 6 couleurs de la conjecture de Hadwiger^[21].
• 1997 :
  • Jeong Han Kim (en), pour ses travaux sur les nombres de Ramsey^[22].
• 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)^[23],
  • Michele Conforti, Gérard Cornuéjols et Mendu Rammohan Rao (en), pour la décomposition des matrices équilibrées (en)^[24],[25].
• 2003 :
  • Jim Geelen, A. M. H. Gerards et A. Kapoor^[26],[27], pour des avancées sur la conjecture de Rota (en) à propos des mineurs de matroïdes (en),
  • Bertrand Guenin^[28],[27], pour sa caractérisation par mineurs exclus (en) 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^{[29],[30],[27]}.
• 2006 :
  • Manindra Agrawal, Neeraj Kayal et Nitin Saxena pour le test de primalité AKS^{[31],[32],[33]} ;
  • Mark Jerrum, Alistair Sinclair et Eric Vigoda pour l'approximation du permanent^[34],[33] ;
  • 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)^[35],[33].
• 2009 :
  • Maria Chudnovsky, Neil Robertson, Paul Seymour, et Robin Thomas pour leur preuve du théorème fort des graphes parfaits^[36],[37].
  • Daniel Spielman et Shang-Hua Teng pour leurs travaux sur l'analyse lisse d'algorithme (smoothed analysis)^[38],[37].
  • Thomas Hales et Samuel P. Ferguson, pour leur démonstration de la conjecture de Kepler^{[39],[40],[37]}.
• 2012 :
  • Sanjeev Arora, Satish Rao (en) et Umesh Vazirani pour leur amélioration de la complexité des algorithmes d'approximation pour calculer les séparateurs de graphe (de O(log n) à O(√log n)) et leurs progrès sur des problèmes liés^[41];
  • 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^[42] ;
  • 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^[43].
• 2015 :
  • Francisco Santos Leal (en) pour son contre-exemple de la conjecture de Hirsch^[44].
• 2018 :
  • Robert Morris, Yoshiharu Kohayakawa, Simon Griffiths, Peter Allen, et Julia Böttcher pour The chromatic thresholds of graphs
  • Thomas Rothvoss (de) pour The Matching Polytope has Exponential Extension Complexity^[45]
• 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 Mikkel Thorup (en) pour Deterministic Edge Connectivity in Near-Linear Time