Premio Fulkerson

Premio a los avances en matemáticas discretas

Otorgar

El Premio Fulkerson para trabajos destacados en el área de las matemáticas discretas es patrocinado conjuntamente por la Sociedad de Optimización Matemática (MOS) y la Sociedad Matemática Americana (AMS). Se entregan hasta tres premios de 1.500 dólares cada uno en cada Simposio Internacional (trienal) de la MOS. Originalmente, los premios se pagaban con un fondo conmemorativo administrado por la AMS que fue establecido por amigos del difunto Delbert Ray Fulkerson para alentar la excelencia matemática en los campos de investigación ejemplificados por su trabajo. Los premios ahora están financiados por una dotación administrada por la MPS.

Ganadores

• 1979:
  • Richard M. Karp por clasificar muchos problemas NP-completos importantes. ^[1]
  • Kenneth Appel y Wolfgang Haken para el teorema de los cuatro colores . ^[2]
  • Paul Seymour por generalizar el teorema de corte mínimo de flujo máximo a los matroides . ^[3]
• 1982:
  • DB Judin, Arkadi Nemirovski , Leonid Khachiyan , Martin Grötschel , László Lovász y Alexander Schrijver por el método del elipsoide en programación lineal y optimización combinatoria . ^{[4] [5] [6] [7]}
  • GP Egorychev y DI Falikman por demostrar la conjetura de van der Waerden de que la matriz con todas las entradas iguales tiene la permanente más pequeña de cualquier matriz doblemente estocástica . ^{[8] [9]}
• 1985:
  • Jozsef Beck propone límites estrictos para la discrepancia de las progresiones aritméticas . ^[10]
  • HW Lenstra Jr. por utilizar la geometría de los números para resolver programas enteros con pocas variables en el tiempo polinomial en el número de restricciones. ^[11]
  • Eugene M. Luks para un algoritmo de isomorfismo de gráficos de tiempo polinomial para gráficos de grado máximo acotado . ^{[12] [13]}
• 1988:
  • Éva Tardos para encontrar circulaciones de costo mínimo en tiempo fuertemente polinomial . ^[14]
  • Narendra Karmarkar por el algoritmo de Karmarkar para programación lineal . ^[15]
• 1991:
  • Martin E. Dyer , Alan M. Frieze y Ravindran Kannan para algoritmos de aproximación basados ​​en recorrido aleatorio para el volumen de cuerpos convexos. ^[16]
  • Alfred Lehman para análogos de matriz 0,1 de la teoría de grafos perfectos . ^[17]
  • Nikolai E. Mnev para el teorema de universalidad de Mnev , que todo conjunto semialgebraico es equivalente al espacio de realizaciones de un matroide orientado . ^[18]
• 1994:
  • Louis Billera por encontrar bases de espacios de funciones polinomiales por partes sobre triangulaciones del espacio. ^[19]
  • Gil Kalai por avanzar en la conjetura de Hirsch al demostrar límites subexponenciales en el diámetro de politopos de dimensión d con n facetas. ^[20]
  • Neil Robertson , Paul Seymour y Robin Thomas para el caso de seis colores de la conjetura de Hadwiger . ^[21]
• 1997:
  • Jeong Han Kim por encontrar la tasa de crecimiento asintótico de los números de Ramsey R (3, t ). ^[22]
• Año 2000:
  • Michel X. Goemans y David P. Williamson para algoritmos de aproximación basados ​​en programación semidefinida . ^[23]
  • Michele Conforti, Gérard Cornuéjols y MR Rao por reconocer matrices 0-1 balanceadas en tiempo polinomial . ^{[24] [25]}
• 2003:
  • JF Geelen , AMH Gerards y A. Kapoor para el caso GF(4) de la conjetura de Rota sobre menores matroides . ^{[26] [27]}
  • Bertrand Guenin para una caracterización menor prohibida de los grafos débilmente bipartitos (grafos cuyo politopo subgráfico bipartito es 0-1). ^{[28] [27]}
  • Satoru Iwata, Lisa Fleischer, Satoru Fujishige y Alexander Schrijver por demostrar que la minimización submodular es fuertemente polinomial. ^{[29] [30] [27]}
• 2006:
  • Manindra Agrawal , Neeraj Kayal y Nitin Saxena , por la prueba de primalidad de AKS . ^{[31] [32] [33]}
  • Mark Jerrum , Alistair Sinclair y Eric Vigoda, por aproximarse a la permanente . ^{[34] [33]}
  • Neil Robertson y Paul Seymour , por el teorema de Robertson-Seymour que muestra que los menores de grafos forman un cuasiordenamiento bien ordenado . ^{[35] [33]}
• 2009:
  • Maria Chudnovsky , Neil Robertson, Paul Seymour y Robin Thomas, por el teorema del grafo perfecto fuerte . ^{[36] [37]}
  • Daniel A. Spielman y Shang-Hua Teng , por el análisis suavizado de algoritmos de programación lineal . ^{[38] [37]}
  • Thomas C. Hales y Samuel P. Ferguson, por demostrar la conjetura de Kepler sobre los empaquetamientos de esferas más densos posibles . ^{[39] [40] [37]}
• 2012:
  • Sanjeev Arora , Satish Rao y Umesh Vazirani por mejorar la relación de aproximación para separadores de gráficos y problemas relacionados de a . ^[41] ${\displaystyle O(\log n)}$ ${\displaystyle O({\sqrt {\log n}})}$
  • Anders Johansson, Jeff Kahn y Van H. Vu para determinar el umbral de densidad de aristas por encima del cual un gráfico aleatorio puede estar cubierto por copias disjuntas de un gráfico más pequeño dado. ^[42]
  • László Lovász y Balázs Szegedy por caracterizar la multiplicidad de subgrafos en secuencias de gráficos densos . ^[43]
• 2015:
  • Francisco Santos Leal para un contraejemplo de la conjetura de Hirsch . ^{[44] [45]}
• 2018:
  • Robert Morris , Yoshiharu Kohayakawa , Simon Griffiths, Peter Allen y Julia Böttcher por Los umbrales cromáticos de los gráficos
  • Thomas Rothvoss por su trabajo sobre la complejidad de extensión del politopo coincidente . ^[46]
• 2021:
  • Béla Csaba, Daniela Kühn , Allan Lo, Deryk Osthus y Andrew Treglown por la demostración de las conjeturas de descomposición de Hamilton y factorización 1
  • Jin-Yi Cai y Xi Chen para la complejidad del conteo de CSP con pesos complejos
  • Ken-Ichi Kawarabayashi y Mikkel Thorup para la conectividad de borde determinista en tiempo casi lineal

Fuente: Sitio web oficial de la Sociedad de Optimización Matemática. ^[47]

• 2024:
  • Ben Cousins ​​y Santosh Vempala para enfriamiento gaussiano y algoritmos para volumen y volumen gaussiano ${\displaystyle O^{*}(n^{3})}$
  • Zilin Jiang, Jonathan Tidor, Yuan Yao, Shengtong Zhang y Yufei Zhao por líneas equiangulares con un ángulo fijo
  • Nathan Keller y Noam Lifshitz para El método de la junta para hipergrafos y la conjetura símplex de Erdős–Chvátal

Fuente: Sitio web oficial de la American Mathematical Society. ^[48]

Véase también

• Lista de premios de matemáticas

Referencias

1. Karp, Richard M. (1975). "Sobre la complejidad computacional de los problemas combinatorios". Redes . 5 : 45–68. doi :10.1002/net.1975.5.1.45.
2. Appel, Kenneth ; Haken, Wolfgang (1977). "Cada mapa planar es coloreable en cuatro colores, Parte I: Descarga". Illinois Journal of Mathematics . 21 : 429–490.
3. Seymour, Paul (1977). "Los matroides con la propiedad de flujo máximo y corte mínimo". Journal of Combinatorial Theory . 23 (2–3): 189–222. doi : 10.1016/0095-8956(77)90031-4 .
4. Judin, DB; Nemirovski, Arkadi (1976). "Complejidad informativa y métodos efectivos de solución para problemas extremales convexos". Ekonomika I Matematicheskie Metody . 12 : 357–369.
5. Khachiyan, Leonid (1979). "Un algoritmo polinómico en programación lineal". Akademiia Nauk SSSR. Doklady . 244 : 1093-1096.
6. "Leonid Khachiyan, profesor y destacado científico informático". Boston Globe . 5 de mayo de 2005..
7. Grötschel, Martin; Lovász, László ; Schrijver, Alexander (1981). "El método del elipsoide y sus consecuencias en la optimización combinatoria". Combinatorica . 1 (2): 169–197. doi :10.1007/bf02579273.
8. Egorychev, médico de cabecera (1981). "La solución del problema de van der Waerden para los permanentes". Akademiia Nauk SSSR. Doklady . 258 : 1041-1044.
9. Falikman, DI (1981). "Una prueba de la conjetura de van der Waerden sobre la permanente de una matriz doblemente estocástica". Matematicheskie Zametki . 29 : 931–938.
10. Beck, Jozsef (1981). "La estimación de Roth de la discrepancia de secuencias de números enteros es casi precisa". Combinatorica . 1 (4): 319–325. doi :10.1007/bf02579452.
11. Lenstra, HW Jr. (1983). "Programación entera con un número fijo de variables". Matemáticas de la investigación de operaciones . 8 (4): 538–548. CiteSeerX 10.1.1.431.5444 . doi :10.1287/moor.8.4.538. 
12. Luks, Eugene M. (1982). "El isomorfismo de gráficos de valencia acotada puede probarse en tiempo polinomial". Journal of Computer and System Sciences . 25 (1): 42–65. doi : 10.1016/0022-0000(82)90009-5 .
13. "El jefe de informática de la U de O obtiene el máximo galardón". Eugene Register-Guard . 10 de agosto de 1985..
14. Tardos, Éva (1985). "Un algoritmo de circulación de costo mínimo fuertemente polinomial". Combinatorica . 5 (3): 247–256. doi :10.1007/bf02579369.
15. Karmarkar, Narendra (1984). "Un nuevo algoritmo de tiempo polinomial para programación lineal". Combinatorica . 4 (4): 373–395. doi :10.1007/bf02579150.
16. Dyer, Martin E. ; Frieze, Alan M. ; Kannan, Ravindran (1991). "Un algoritmo de tiempo polinomial aleatorio para aproximar el volumen de cuerpos convexos". Revista de la ACM . 38 (1): 1–17. CiteSeerX 10.1.1.145.4600 . doi :10.1145/102782.102783. 
17. Alfred Lehman, "La desigualdad ancho-longitud y los planos proyectivos degenerados", W. Cook y PD Seymour (eds.), Combinatoria poliédrica, Serie DIMACS en Matemáticas discretas y Ciencias de la computación teórica, volumen 1, (Sociedad Matemática Americana, 1990) pp. 101-105.
18. Nikolai E. Mnev, "Los teoremas de universalidad en el problema de clasificación de variedades de configuración y variedades de politopos convexos", O. Ya. Viro (ed.), Topología y geometría-Seminario Rohlin, Apuntes de clase en matemáticas 1346 (Springer-Verlag, Berlín, 1988) pp. 527-544.
19. Billera, Louis (1988). "Homología de splines suaves: triangulaciones genéricas y una conjetura de Strang". Transactions of the American Mathematical Society . 310 (1): 325–340. doi : 10.2307/2001125 . JSTOR  2001125.
20. Kalai, Gil (1992). "Límites superiores para el diámetro y la altura de los gráficos de los poliedros convexos". Geometría discreta y computacional . 8 (4): 363–372. doi : 10.1007/bf02293053 .
21. Robertson, Neil ; Seymour, Paul ; Thomas, Robin (1993). "Conjetura de Hadwiger para grafos libres de K_6". Combinatorica . 13 (3): 279–361. doi :10.1007/bf01202354.
22. Kim, Jeong Han (1995). "El número de Ramsey R (3, t ) tiene un orden de magnitud t ² /log  t ". Random Structures & Algorithms . 7 (3): 173–207. doi :10.1002/rsa.3240070302. MR  1369063..
23. Goemans, Michel X.; Williamson, David P. (1995). "Algoritmos de aproximación mejorados para los problemas de corte máximo y satisfacibilidad utilizando programación semidefinida". Revista de la ACM . 42 (6): 1115–1145. doi : 10.1145/227683.227684 .
24. Michele Conforti, Gérard Cornuéjols y MR Rao , "Descomposición de matrices balanceadas", Journal of Combinatorial Theory , Serie B, 77 (2): 292–406, 1999.
25. "El Sr. Rao, nuevo decano de la ISB". Financial Express . 2 de julio de 2004..
26. JF Geelen , AMH Gerards y A. Kapoor, "Los menores excluidos para matroides representables por GF(4)", Journal of Combinatorial Theory , Serie B, 79 (2): 247–2999, 2000.
27. Cita del Premio Fulkerson 2003, consultado el 18 de agosto de 2012.
28. Bertrand Guenin, "Una caracterización de grafos débilmente bipartitos", Journal of Combinatorial Theory , Serie B, 83 (1): 112–168, 2001.
29. Satoru Iwata, Lisa Fleischer, Satoru Fujishige, "Un algoritmo combinatorio fuertemente polinomial para minimizar funciones submodulares", Journal of the ACM , 48 (4): 761–777, 2001.
30. Alexander Schrijver , "Un algoritmo combinatorio que minimiza funciones submodulares en tiempo fuertemente polinomial", Journal of Combinatorial Theory , Serie B 80 (2): 346–355, 2000.
31. Manindra Agrawal , Neeraj Kayal y Nitin Saxena , "PRIMES está en P", Annals of Mathematics , 160 (2): 781–793, 2004.
32. Raghunathan, MS (11 de junio de 2009). "India como actor en las matemáticas". The Hindu . Archivado desde el original el 14 de junio de 2009..
33. Cita del Premio Fulkerson 2006, consultado el 19 de agosto de 2012.
34. Mark Jerrum , Alistair Sinclair y Eric Vigoda, "Un algoritmo de aproximación en tiempo polinomial para la permanente de una matriz con entradas no negativas", Journal of the ACM , 51 (4): 671–697, 2004.
35. Neil Robertson y Paul Seymour , "Graph Minors. XX. La conjetura de Wagner", Journal of Combinatorial Theory , Serie B, 92 (2): 325–357, 2004.
36. Chudnovsky, Maria ; Robertson, Neil; Seymour, Paul; Thomas, Robin (2006). "El teorema del grafo perfecto fuerte". Anales de Matemáticas . 164 : 51–229. arXiv : math/0212070 . doi :10.4007/annals.2006.164.51.
37. Cita del Premio Fulkerson 2009, consultado el 19 de agosto de 2012.
38. Spielman, Daniel A. ; Teng, Shang-Hua (2004). "Análisis suavizado de algoritmos: por qué el algoritmo simplex suele tardar un tiempo polinomial". Revista de la ACM . 51 : 385–463. arXiv : math/0212413 . doi :10.1145/990308.990310.
39. Hales, Thomas C. (2005). "Una prueba de la conjetura de Kepler". Anales de Matemáticas . 162 (3): 1063–1183. doi : 10.4007/annals.2005.162.1065 .
40. Ferguson, Samuel P. (2006). "Empaquetamientos de esferas, V. Prismas pentaédricos". Geometría discreta y computacional . 36 : 167–204. doi : 10.1007/s00454-005-1214-y .
41. Arora, Sanjeev ; Rao, Satish; Vazirani, Umesh (2009). "Flujos de expansión, incrustaciones geométricas y particionamiento de grafos". Revista de la ACM . 56 (2): 1–37. CiteSeerX 10.1.1.310.2258 . doi :10.1145/1502793.1502794. 
42. Johansson, Anders; Kahn, Jeff ; Vu, Van H. (2008). "Factores en grafos aleatorios". Estructuras y algoritmos aleatorios . 33 : 1–28. doi :10.1002/rsa.20224.
43. Lovász, László ; Szegedy, Balázs (2006). "Límites de secuencias de gráficos densas". Revista de teoría combinatoria . 96 (6): 933–957. arXiv : matemáticas/0408173 . doi :10.1016/j.jctb.2006.05.002.
44. Santos, Francisco (2011). "Un contraejemplo a la conjetura de Hirsch". Anales de Matemáticas . 176 (1): 383–412. arXiv : 1006.2814 . doi :10.4007/annals.2012.176.1.7. MR  2925387.
45. Cita del Premio Fulkerson 2015, consultado el 18 de julio de 2015.
46. Rothvoß, Thomas (2017). "El politopo coincidente tiene complejidad de extensión exponencial". Revista de la ACM . 64 (6): A41:1–A41:19. arXiv : 1311.2369 . doi :10.1145/3127497. MR  3713797.
47. "El premio Fulkerson". Premios MOS . Sociedad de Optimización Matemática . Consultado el 25 de julio de 2024 .
48. "Se otorga el premio Delbert Ray Fulkerson 2024". Noticias de la AMS . American Mathematical Society. 23 de julio de 2024 . Consultado el 25 de julio de 2024 .

Enlaces externos

• Página web oficial (MOS)
• Sitio oficial con detalles del premio (sitio web de AMS)
• Archivo AMS de ganadores de premios anteriores