Premio Fulkerson

Premio a los avances en matemáticas discretas.

Otorgar

El Premio Fulkerson para trabajos destacados en el área de matemáticas discretas está patrocinado conjuntamente por la Mathematical Optimization Society (MOS) y la American Mathematical Society (AMS). En cada Simposio Internacional (trienal) de la MOS se entregan hasta tres premios de 1.500 dólares cada uno. Originalmente, los premios se pagaron con cargo a un fondo conmemorativo administrado por la AMS que fue establecido por amigos del fallecido Delbert Ray Fulkerson para fomentar la excelencia matemática en los campos de investigación ejemplificados por su trabajo. Los premios ahora están financiados por una donación administrada por MPS.

Ganadores

Fuente: Sociedad de Optimización Matemática

• 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 matroides ". ^[3]
• mil novecientos ochenta y dos:
  • 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 el permanente más pequeño de cualquier matriz doblemente estocástica . ^{[8] [9]}
• 1985:
  • Jozsef Beck por los límites estrictos a la discrepancia de las progresiones aritméticas . ^[10]
  • HW Lenstra Jr. por utilizar la geometría de números para resolver programas enteros con pocas variables en tiempo polinómico en el número de restricciones. ^[11]
  • Eugene M. Luks para un algoritmo de isomorfismo de gráficos de tiempo polinómico para gráficos de grado máximo acotado . ^{[12] [13]}
• 1988:
  • Éva Tardos por encontrar circulaciones de coste mínimo en tiempos fuertemente polinomiales . ^[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 paseos aleatorios para el volumen de cuerpos convexos. ^[dieciséis]
  • Alfred Lehman para análogos de matriz 0,1 de la teoría de gráficos perfectos . ^[17]
  • Nikolai E. Mnev por el teorema de universalidad de Mnev , de que todo conjunto semialgebraico es equivalente al espacio de realizaciones de una matroide orientada . ^[18]
• 1994:
  • Louis Billera por encontrar bases de espacios funcionales 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 d -dimensionales 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ótica de los números de Ramsey R (3, t ). ^[22]
• 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 equilibradas 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 por una caracterización menor prohibida de los grafos débilmente bipartitos (gráficos cuyo politopo de subgrafo bipartito es 0-1). ^{[28] [27]}
  • Satoru Iwata, Lisa Fleischer, Satoru Fujishige y Alexander Schrijver por demostrar que la minimización submodular es fuertemente polinómica. ^{[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 aproximarnos al permanente . ^{[34] [33]}
  • Neil Robertson y Paul Seymour , por el teorema de Robertson-Seymour que muestra que los grafos menores forman un cuasiordenamiento bien . ^{[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 un análisis simplificado de algoritmos de programación lineal . ^{[38] [37]}
  • Thomas C. Hales y Samuel P. Ferguson, por demostrar la conjetura de Kepler sobre los empaquetamientos esféricos 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 por determinar el umbral de densidad de bordes por encima del cual un gráfico aleatorio puede cubrirse con 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 la extensión del politopo correspondiente . ^[46]
• 2021:
  • Béla Csaba, Daniela Kühn , Allan Lo, Deryk Osthus y Andrew Treglown por la prueba de las conjeturas de factorización 1 y descomposición de Hamilton
  • Jin-Yi Cai y Xi Chen por la complejidad del recuento de CSP con pesos complejos
  • Ken-Ichi Kawarabayashi y Mikkel Thorup para la conectividad de borde determinista en tiempo casi lineal

Ver 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. Apelar, Kenneth ; Haken, Wolfgang (1977). "Cada mapa plano tiene cuatro colores, Parte I: Descarga". Revista de Matemáticas de Illinois . 21 : 429–490.
3. Seymour, Paul (1977). "Las matroides con la propiedad max-flow min-cut". Revista de teoría combinatoria . 23 : 189–222. doi : 10.1016/0095-8956(77)90031-4 .
4. Judin, DB; Nemirovski, Arkadi (1976). "Complejidad informativa y métodos eficaces de solución de problemas extremos convexos". Metodología Ekonomika i Matematicheskie . 12 : 357–369.
5. Khachiyan, Leonid (1979). "Un algoritmo polinomial en programación lineal". Akademiia Nauk SSSR. Doklady . 244 : 1093-1096.
6. "Leonid Khachiyan, profesor, destacado científico informático". Globo de Boston . 5 de mayo de 2005..
7. Grötschel, Martín; Lovász, László ; Schrijver, Alejandro (1981). "El método del elipsoide y sus consecuencias en la optimización combinatoria". Combinatoria . 1 : 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 enteras es casi nítida". Combinatoria . 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áficas de valencia acotada se puede probar en tiempo polinómico". Revista de Ciencias de la Computación y de Sistemas . 25 (1): 42–65. doi : 10.1016/0022-0000(82)90009-5 .
13. "El jefe de informática de la U of O obtiene el máximo premio". Registro-Guardia de Eugene . 10 de agosto de 1985..
14. Tardos, Éva (1985). "Un algoritmo de circulación de coste mínimo fuertemente polinómico". Combinatoria . 5 : 247–256. doi :10.1007/bf02579369.
15. Karmarkar, Narendra (1984). "Un nuevo algoritmo de tiempo polinomial para programación lineal". Combinatoria . 4 : 373–395. doi :10.1007/bf02579150.
16. Dyer, Martín E .; Friso, Alan M .; Kannan, Ravindran (1991). "Un algoritmo de tiempo polinómico 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-largo y los planos proyectivos degenerados", W. Cook y PD Seymour (eds.), Combinatoria poliédrica, Serie DIMACS en matemáticas discretas e informática teórica, volumen 1, (Sociedad Matemática Estadounidense, 1990) págs. 101-105.
18. Nikolai E. Mnev, "Los teoremas de universalidad sobre el problema de clasificación de variedades de configuración y variedades de politopos convexos", O. Ya. Viro (ed.), Topology and Geometry-Rohlin Seminar, Lecture Notes in Mathematics 1346 (Springer-Verlag, Berlín, 1988) págs.
19. Billera, Luis (1988). "Homología de splines suaves: triangulaciones genéricas y una conjetura de Strang". Transacciones de la Sociedad Matemática Estadounidense . 310 : 325–340. doi : 10.2307/2001125 .
20. Kalai, Gil (1992). "Límites superiores para el diámetro y la altura de las gráficas de los poliedros convexos". Geometría Discreta y Computacional . 8 : 363–372. doi : 10.1007/bf02293053 .
21. Robertson, Neil ; Seymour, Pablo ; Thomas, Robin (1993). "Conjetura de Hadwiger para gráficos libres de K_6". Combinatoria . 13 : 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 ". Algoritmos y estructuras aleatorias . 7 (3): 173–207. doi :10.1002/rsa.3240070302. SEÑOR  1369063..
23. Goemans, Michel X.; Williamson, David P. (1995). "Algoritmos de aproximación mejorados para el problema de máximo corte y satisfacibilidad mediante 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 equilibradas", Journal of Combinatorial Theory , Serie B, 77 (2): 292–406, 1999.
25. "MR Rao, nuevo decano de la ISB". Expreso Financiero . 2 de julio de 2004..
26. JF Geelen , AMH Gerards y A. Kapoor, "Los menores excluidos de las matroides representables GF(4)", Journal of Combinatorial Theory , Serie B, 79 (2): 247–2999, 2000.
27. Cita del premio Fulkerson abc 2003, consultado el 18 de agosto de 2012.
28. Bertrand Guenin, "Una caracterización de gráficos 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 polinómico", 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 matemáticas". El hindú . Archivado desde el original el 14 de junio de 2009..
33. Cita del premio Fulkerson abc 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 el 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. Conjetura de Wagner", Journal of Combinatorial Theory , Serie B, 92 (2): 325–357, 2004.
36. Chudnovsky, María ; Robertson, Neil; Seymour, Pablo; Thomas, Robin (2006). "El teorema del gráfico perfecto fuerte". Anales de Matemáticas . 164 : 51–229. arXiv : matemáticas/0212070 . doi : 10.4007/annals.2006.164.51.
37. Mención del premio Fulkerson abc 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 tomar tiempo polinómico". Revista de la ACM . 51 : 385–463. arXiv : matemáticas/0212413 . doi :10.1145/990308.990310.
39. Hales, Thomas C. (2005). "Una prueba de la conjetura de Kepler". Anales de Matemáticas . 162 : 1063-1183. doi : 10.4007/annals.2005.162.1065 .
40. Ferguson, Samuel P. (2006). "Empaquetaduras 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 expansores, incrustaciones geométricas y partición de gráficos". Revista de la ACM . 56 : 1–37. CiteSeerX 10.1.1.310.2258 . doi :10.1145/1502793.1502794. 
42. Johansson, Anders; Kahn, Jeff ; Vu, Van H. (2008). "Factores en gráficas aleatorias". Estructuras aleatorias y algoritmos . 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 : 933–957. arXiv : matemáticas/0408173 . doi :10.1016/j.jctb.2006.05.002.
44. Santos, Francisco (2011). "Un contraejemplo de la conjetura de Hirsch". Anales de Matemáticas . 176 (1): 383–412. arXiv : 1006.2814 . doi : 10.4007/annals.2012.176.1.7. SEÑOR  2925387.
45. Mención del Premio Fulkerson 2015, consultado el 18 de julio de 2015.
46. Rothvoß, Thomas (2017). "El politopo correspondiente tiene una complejidad de extensión exponencial". Revista de la ACM . 64 (6): A41:1–A41:19. arXiv : 1311.2369 . doi :10.1145/3127497. SEÑOR  3713797.

enlaces externos

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