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 presentan hasta tres premios de $ 1,500 cada uno . Originalmente, los premios se pagaron con un fondo conmemorativo administrado por la AMS que fue establecido por amigos del difunto 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.
Premio Fulkerson | |
---|---|
Otorgado por | Trabajos sobresalientes en el área de matemáticas discretas |
País | Estados Unidos |
Presentado por | Sociedad de Optimización Matemática Sociedad Americana de Matemáticas |
Recompensa (s) | $ 1,500 |
Primer premio | 1979 |
Sitio web | http://www.ams.org/profession/prizes-awards/ams-prizes/fulkerson-prize |
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 flujo máximo y corte mínimo 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 elipsoide en programación lineal y optimización combinatoria . [4] [5] [6] [7]
- GP Egorychev y DI Falikman por probar 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 estrechos en la discrepancia de las progresiones aritméticas . [10]
- HW Lenstra, Jr. por usar la geometría de números para resolver programas enteros con pocas variables en polinomios de tiempo en el número de restricciones. [11]
- Eugene M. Luks para un algoritmo de isomorfismo de gráfico de tiempo polinomial para gráficos de grado máximo acotado . [12] [13]
- 1988:
- Éva Tardos para encontrar circulaciones de coste mínimo en tiempo fuertemente polinomial . [14]
- Narendra Karmarkar para 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 recorridos aleatorios para el volumen de cuerpos convexos. [dieciséis]
- 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 una matroide orientada . [18]
- 1994:
- Louis Billera por encontrar bases de espacios funcionales polinomiales por partes sobre triangulaciones de espacio. [19]
- Gil Kalai por progresar 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 por 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 los menores matroides . [26] [27]
- Bertrand Guenin por una caracterización menor prohibida de los grafos débilmente bipartitos (grafos cuyo politopo de subgrafo bipartito es 0-1). [28] [27]
- Satoru Iwata, Lisa Fleischer, Satoru Fujishige y Alexander Schrijver por mostrar que la minimización submodular es fuertemente polinomial. [29] [30] [27]
- 2006:
- Manindra Agrawal , Neeraj Kayal y Nitin Saxena , para la prueba de primalidad AKS . [31] [32] [33]
- Mark Jerrum , Alistair Sinclair y Eric Vigoda, por aproximarse a lo permanente . [34] [33]
- Neil Robertson y Paul Seymour , para el teorema de Robertson-Seymour que muestra que los grafos menores forman un cuasi-ordenamiento bien . [35] [33]
- 2009:
- Maria Chudnovsky , Neil Robertson, Paul Seymour y Robin Thomas, para el teorema del grafo perfecto fuerte . [36] [37]
- Daniel A. Spielman y Shang-Hua Teng , para un análisis suavizado de algoritmos de programación lineal . [38] [37]
- Thomas C. Hales y Samuel P. Ferguson, por probar la conjetura de Kepler sobre las empaquetaduras de esferas más densas . [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]
- 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áficas densas . [43]
- 2015:
- Francisco Santos Leal por 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 para The Matching Polytope tiene una complejidad de extensión exponencial
Ver también
- Lista de premios de matemáticas
Referencias
- ^ Karp, Richard M. (1975). "Sobre la complejidad computacional de problemas combinatorios". Redes . 5 : 45–68. doi : 10.1002 / net.1975.5.1.45 .
- ^ Appel, Kenneth ; Haken, Wolfgang (1977). "Cada mapa plano tiene cuatro colores, Parte I: Descarga". Revista de Matemáticas de Illinois . 21 : 429–490.
- ^ 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 .
- ^ Judin, DB; Nemirovski, Arkadi (1976). "Complejidad informativa y métodos eficaces de solución de problemas extremos convexos". Ekonomika i Matematicheskie Metody . 12 : 357–369.
- ^ Khachiyan, Leonid (1979). "Un algoritmo polinomial en programación lineal". Akademiia Nauk SSSR. Doklady . 244 : 1093–1096.
- ^ "Leonid Khachiyan, profesor, científico informático líder" , Boston Globe , 5 de mayo de 2005.
- ^ Grötschel, Martin; Lovász, László ; Schrijver, Alexander (1981). "El método elipsoide y sus consecuencias en la optimización combinatoria". Combinatorica . 1 : 169-197. doi : 10.1007 / bf02579273 .
- ^ Egorychev, GP (1981). "La solución del problema de van der Waerden para permanentes". Akademiia Nauk SSSR. Doklady . 258 : 1041-1044.
- ^ Falikman, DI (1981). "Una prueba de la conjetura de van der Waerden sobre el permanente de una matriz doblemente estocástica". Matematicheskie Zametki . 29 : 931–938.
- ^ Beck, Jozsef (1981). "La estimación de Roth de la discrepancia de secuencias enteras es casi nítida". Combinatorica . 1 (4): 319–325. doi : 10.1007 / bf02579452 .
- ^ Lenstra, HW ; Jr (1983). "Programación de enteros con un número fijo de variables". Matemáticas de la investigación operativa . 8 (4): 538–548. CiteSeerX 10.1.1.431.5444 . doi : 10.1287 / moor.8.4.538 .
- ^ Luks, Eugene M. (1982). "El isomorfismo de gráficos de valencia limitada se puede probar en tiempo polinomial" . Revista de Ciencias de la Computación y Sistemas . 25 (1): 42–65. doi : 10.1016 / 0022-0000 (82) 90009-5 .
- ^ "U of O Computer Chief Gets Top Award" , Eugene Register-Guard , 10 de agosto de 1985.
- ^ Tardos, Éva (1985). "Un algoritmo de circulación de coste mínimo fuertemente polinomial". Combinatorica . 5 : 247-256. doi : 10.1007 / bf02579369 .
- ^ Karmarkar, Narendra (1984). "Un nuevo algoritmo de tiempo polinomial para la programación lineal". Combinatorica . 4 : 373–395. doi : 10.1007 / bf02579150 .
- ^ 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 .
- ^ Alfred Lehman, "La desigualdad de ancho-longitud y 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, (American Mathematical Society, 1990) págs. 101-105.
- ^ Nikolai E. Mnev, "Los teoremas de la universalidad sobre el problema de clasificación de las variedades de configuración y las variedades politopo convexas", O. Ya. Viro (ed.), Seminario de topología y geometría-Rohlin, Lecture Notes in Mathematics 1346 (Springer-Verlag, Berlín, 1988) pp. 527-544.
- ^ Billera, Louis (1988). "Homología de splines suaves: triangulaciones genéricas y una conjetura de Strang" . Transacciones de la American Mathematical Society . 310 : 325–340. doi : 10.2307 / 2001125 .
- ^ 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 .
- ^ Robertson, Neil ; Seymour, Paul ; Thomas, Robin (1993). "Conjetura de Hadwiger para gráficos sin K_6". Combinatorica . 13 : 279–361. doi : 10.1007 / bf01202354 .
- ^ Kim, Jeong Han (1995), "El número de Ramsey R (3, t ) tiene un orden de magnitud t 2 / log t ", Estructuras y algoritmos aleatorios , 7 (3): 173-207, doi : 10.1002 / rsa.3240070302 , MR 1369063.
- ^ Goemans, Michel X .; Williamson, David P. (1995). "Algoritmos de aproximación mejorados para el máximo problema de corte y satisfacibilidad utilizando programación semi-definida". Revista de la ACM . 42 (6): 1115-1145. doi : 10.1145 / 227683.227684 .
- ^ Michele Conforti, Gérard Cornuéjols y MR Rao , "Descomposición de matrices equilibradas", Revista de teoría combinatoria , Serie B, 77 (2): 292–406, 1999.
- ^ "MR Rao New Dean Of ISB" , Financial Express , 2 de julio de 2004.
- ^ JF Geelen , AMH Gerards y A. Kapoor, "Los menores excluidos de GF (4) -Representable Matroids", Journal of Combinatorial Theory , Serie B, 79 (2): 247-2999, 2000.
- ^ a b c Cita del premio Fulkerson 2003, consultado el 18 de agosto de 2012 .
- ^ Bertrand Guenin, "Una caracterización de gráficos débilmente bipartitos", Journal of Combinatorial Theory , Serie B, 83 (1): 112-168, 2001.
- ^ Satoru Iwata, Lisa Fleischer, Satoru Fujishige, "Un algoritmo combinatorio fuertemente polinomial para minimizar las funciones submodulares", Journal of the ACM , 48 (4): 761–777, 2001.
- ^ Alexander Schrijver , "Un algoritmo combinatorio que minimiza las funciones submodulares en el tiempo fuertemente polinomial", Journal of Combinatorial Theory , Serie B 80 (2): 346–355, 2000.
- ^ Manindra Agrawal , Neeraj Kayal y Nitin Saxena , "PRIMES está en P", Annals of Mathematics , 160 (2): 781-793, 2004.
- ^ Raghunathan, MS (11 de junio de 2009), "India como jugador en matemáticas" , The Hindu , archivado desde el original el 14 de junio de 2009.
- ^ a b c Cita del premio Fulkerson 2006, consultado el 19 de agosto de 2012 .
- ^ Mark Jerrum , Alistair Sinclair y Eric Vigoda , "Un algoritmo de aproximación de tiempo polinomial para el permanente de una matriz con entradas no negativas", Journal of the ACM , 51 (4): 671-697, 2004.
- ^ Neil Robertson y Paul Seymour , "Graph Minors. XX. Conjetura de Wagner", Journal of Combinatorial Theory , Serie B, 92 (2): 325-357, 2004.
- ^ Chudnovsky, Maria ; Robertson, Neil; Seymour, Paul; Thomas, Robin (2006). "El teorema del gráfico perfecto fuerte". Annals of Mathematics . 164 : 51-229. arXiv : matemáticas / 0212070 . doi : 10.4007 / annals.2006.164.51 .
- ^ a b c Cita del premio Fulkerson 2009, consultado el 19 de agosto de 2012 .
- ^ Spielman, Daniel A .; Teng, Shang-Hua (2004). "Análisis suavizado de algoritmos: por qué el algoritmo simplex suele tomar tiempo polinomial". Revista de la ACM . 51 : 385–463. arXiv : matemáticas / 0212413 . doi : 10.1145 / 990308.990310 .
- ^ Hales, Thomas C. (2005). "Una prueba de la conjetura de Kepler" . Annals of Mathematics . 162 : 1063-1183. doi : 10.4007 / annals.2005.162.1065 .
- ^ Ferguson, Samuel P. (2006). "Empaquetaduras de esfera, prismas pentaédricos V." . Geometría discreta y computacional . 36 : 167-204. doi : 10.1007 / s00454-005-1214-y .
- ^ Arora, Sanjeev ; Rao, Satish; Vazirani, Umesh (2009). "Flujos expansores, incrustaciones geométricas y particiones gráficas". Revista de la ACM . 56 : 1-37. CiteSeerX 10.1.1.310.2258 . doi : 10.1145 / 1502793.1502794 .
- ^ Johansson, Anders; Kahn, Jeff ; Vu, Van H. (2008). "Factores en gráficos aleatorios". Estructuras y algoritmos aleatorios . 33 : 1–28. doi : 10.1002 / rsa.20224 .
- ^ Lovász, László ; Szegedy, Balázs (2006). "Límites de secuencias de gráficos densos". Revista de teoría combinatoria . 96 : 933–957. arXiv : matemáticas / 0408173 . doi : 10.1016 / j.jctb.2006.05.002 .
- ^ Santos, Francisco (2011), "Un contraejemplo de la conjetura de Hirsch", Annals of Mathematics , 176 (1): 383–412, arXiv : 1006.2814 , doi : 10.4007 / annals.2012.176.1.7 , MR 2925387
- ^ Cita del premio Fulkerson 2015, consultado el 18 de julio de 2015 .
enlaces externos
- Página web oficial (MOS)
- Sitio oficial con detalles del premio (sitio web de AMS)
- Archivo AMS de ganadores de premios anteriores