El Premio Fulkerson es un premio científico al trabajo destacado en el campo de las matemáticas discretas , presentado conjuntamente por la Mathematical Optimization Society (MOS) y la American Mathematical Society (AMS) en el Simposio Internacional de MOS, que tiene lugar cada tres años. . En cada uno de estos eventos, se anuncian más de tres nominaciones, cada una de las cuales puede incluir varios científicos. El premio, $ 1500 , se pagó originalmente de un fondo establecido por amigos de Delbert Ray Fulkerson después de su muerte para apoyar el trabajo matemático en su campo.
| Año | Laureados | ¿Para qué fue el premio? |
|---|---|---|
| 1979 | ricardo karpe | para clasificar muchos problemas NP-completos importantes [1] |
| Kenneth Appel Wolfgang Haken |
para resolver el problema de los cuatro colores [2] | |
| Pablo Seymour | por generalizar el teorema de Ford-Fulkerson a matroides [3] | |
| mil novecientos ochenta y dos | David Yudin Arkady Nemirovsky Leonid Khachiyan |
para el método de elipsoides en programación lineal [4] [5] |
| Georgy Egorychev Dmitry Falikman |
para probar la conjetura de van der Waerden sobre el permanente de una matriz doblemente estocástica [6] | |
| Martin Grötschel Laszlo Lovas Alexander Schreiver |
para el método del elipsoide en optimización combinatoria [7] | |
| 1985 | José Beck | para estimar los límites de divergencia de secuencias enteras [8] |
| Hendrik Lenstra | para un método eficiente para resolver programas enteros usando la geometría de números [9] | |
| Eugenio Luks | para un algoritmo polinomial para determinar grafos isomórficos de grado acotado [10] | |
| 1988 | Eva Tardosh | para resolver el problema de flujo de costo mínimo mediante un algoritmo de complejidad fuertemente polinomial [11] |
| Narendra Karmarkar | para el algoritmo Karmarkar [12] | |
| 1991 | Martin Dyer Alan Freese Ravindran Kannan |
para un algoritmo errante para estimar el volumen de cuerpos convexos [13] |
| alfredo lehman | para análogos de matrices binarias en la teoría de grafos perfectos [14] | |
| Nikolái Mnev | por el teorema de universalidad de que cualquier conjunto semialgebraico es equivalente al espacio de realizaciones de una matroide orientada [15] | |
| 1994 | Luis Billera | para encontrar bases para el espacio de funciones parcialmente polinómicas [16] |
| Gil Kalai | para el trabajo sobre la conjetura de Hirsch [17] | |
| Neil Robertson | para la solución de seis colores de la conjetura de Hadwiger [18] | |
| 1997 | Jung Han Kim | para el análisis asintótico de los números de Ramsey R (3, t ) [19] |
| 2000 | Michel Humanos David Williamson |
para algoritmos de aproximación en programación semidefinida [20] |
| Michel Conforti Gerard Cornuejols Mendou Rao |
para el algoritmo de reconocimiento de matrices binarias balanceadas en tiempo polinomial [21] | |
| 2003 | James Galen Bert Gerards Ajay Kapoor |
para la solución GF(4) de la conjetura de Rota para menores matroides [22] |
| Bertrand Gjunin | para caracterizar los menores prohibidos de grafos débilmente bipartitos [23] | |
| Satoru Iwata Lisa Fleischer Satoru Fujishige Lex Shreiver |
para probar la fuerte polinomialidad de la minimización submodular [24] [25] | |
| 2006 | Agrawal Kayal Saxena |
para la prueba Agrawala - Kayala - Sajonia [26] |
| Mark Errum Alistair Sinclair Eric Vigoda |
para la aproximación de lo permanente [27] | |
| Neil Robertson Paul Seymour |
para el teorema de Robertson-Seymour [28] | |
| 2009 | Maria Chudnovskaya Neil Robertson Paul Seymour Robin Thomas |
para el teorema del gráfico fuertemente ideal [29] |
| Daniel Spielman Teng Shanhua |
para análisis suavizado de algoritmos de programación lineal [30] [31] | |
| Thomas Hales Samuel Ferguson |
para probar la conjetura de Kepler para el empaque más denso de bolas [32] [33] | |
| 2012 | Sanjeev Arora Satish Rao Umesh Vazirani |
para reducir la complejidad del algoritmo para aproximar separadores de grafos [34] |
| Anders Johansson Jeff Kahn Wu Ha Wang |
para determinar el límite de densidad de arco con el que un gráfico aleatorio puede cubrirse con copias separadas de un gráfico más pequeño dado [35] | |
| Laszlo Lovas Balazs Szegedi |
para estimar la multiplicidad de subgrafos en secuencias de grafos densos [36] | |
| 2015 | francisco santos | para un contraejemplo a la conjetura de Hirsch [37] |
| 2018 | Peter Allen Julia Boettcher Griffiths Kohayakawa Robert Morris |
para Los umbrales cromáticos de los gráficos |
| Thomas Rothvoss | para The Matching Polytope tiene una complejidad de extensión exponencial | |
| 2021 | Bela Chaba Daniela Kuhn Allan Lo Derek Oustus Andrew Treglow |
para probar la conjetura de factorización 1 y la conjetura de expansión hamiltoniana [38] |
| Cai Jin Xi Chen |
para determinar la complejidad de calcular funciones de partición [39] | |
| Ken-Ichi Kawarabayashi Mikkel Torup |
para desarrollar un algoritmo determinista para determinar la conectividad de borde [40] |