Prêmio Fulkerson

O Prêmio Fulkerson (Delbert Ray Fulkerson Prize) é um prêmio de três anos concedido pela Mathematical Programming Society (MPS) e pela American Mathematical Society (AMS) por um trabalho excepcional em matemática discreta, incluindo combinatória e ciência da computação . Serão concedidos até três prêmios, cada um no valor de $ 1.500. Eles têm o nome de Delbert Ray Fulkerson e foram originalmente financiados por um fundo doado por amigos de Fulkerson em sua memória.

Vencedores do prêmio

  • 1979: Richard M. Karp (para On the computational complex of combinatorial problems , Networks, Vol. 5, 1975, pp. 45-68); Kenneth Appel e Wolfgang Haken (para o conjunto de quatro cores , em Every planar map is four colorable, Part I: Discharging , Illinois Journal of Mathematics, Vol. 21, 1977, pp. 429-490); Paul Seymour (para The matroids with the max-flow min-cut property , Journal of Combinatorial Theory, Series B, Vol. 23, 1977, pp. 189-222).
  • 1982: DB Judin e Arkadi Nemirovski (para Complexidade informacional e métodos eficazes de solução para problemas extremos convexos , Ekonomika i Matematicheskie Metody, Vol. 12, 1976, pp. 357-369); Leonid Khachiyan (para um algoritmo polinomial em programação linear , Akademiia Nauk SSSR. Doklady, Vol. 244, 1979, p. 1073); GP Egorychev (para A solução do problema de van der Waerden para permanentes , Akademiia Nauk SSSR. Doklady, vol. 258, 1981, pp. 1041-1044); DI Falikman (para uma prova da conjectura de van der Waerden sobre a permanente de uma matriz duplamente estocástica , Matematicheskie Zametki, Vol. 29, 1981, pp. 931-938); Martin Grötschel , László Lovász e Alexander Schrijver (para o método elipsóide e suas consequências na otimização combinatória, Combinatorica, Vol. 1, 1981, pp. 169-197).
  • 1985: József Beck (para a estimativa de Roth da discrepância de sequências inteiras é quase nítida , Combinatorica, Vol. 1, 1981, pp. 319-325); Hendrik Lenstra (para programação inteira com um número fixo de variáveis , Mathematics of Operations Research, Vol. 8, 1983, pp. 538-548); Eugene M. Luks (para isomorfismo de gráficos de valência limitada pode ser testado em tempo polinomial , Journal of Computer and System Sciences, Vol. 25, 1982, pp. 42-65).
  • 1988: Éva Tardos (para um algoritmo de circulação de custo mínimo fortemente polinomial , Combinatorica, Vol. 5, 1985, pp. 247-256); Narendra Karmarkar (para um novo algoritmo de tempo polinomial para programação linear , Combinatorica, Vol. 4, 1984, pp. 373-395).
  • 1991: Martin E. Dyer , Alan M. Frieze e Ravindran Kannan (para um algoritmo de tempo polinomial aleatório para aproximar o volume de corpos convexos , Journal of the ACM, Vol. 38, 1991, pp. 1-17); Alfred Lehman (para The width-length inequality and degenerate projective planes , em W. Cook, PD Seymour (editor), Polyhedral Combinatorics , DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 1, American Mathematical Society, 1990, p. 101-105); Nikolai E. Mnev (para os teoremas de universalidade no problema de classificação de variedades de configuração e variedades de politopo convexo , em Oleg Viro (editor), Topology and Geometry-Rohlin Seminar , Lecture Notes in Mathematics Vol. 1346, Springer 1988, p. 527– 544).
  • 1994: Louis Billera (para Homology of smooth splines: Generic triangulations and a conjecture of Strang , Transactions of the AMS, Vol. 310, 1988, pp. 325-340); Gil Kalai (para limites superiores do diâmetro e altura dos gráficos dos poliedros convexos , Discrete and Computational Geometry, Vol. 8, 1992, pp. 363-372); Neil Robertson , Paul Seymour e Robin Thomas (para a conjectura de Hadwiger para K6; gráficos livres , Combinatorica, Vol. 13, 1993, pp. 279-361).
  • 1997: Jeong Han Kim (para The Ramsey Number R (3, t) Has Order of Magnitude t2 / log t , Random Structures and Algorithms, Vol. 7, 1995, pp. 173-207).
  • 2000: Michel X. Goemans e David P. Williamson (para algoritmos de aproximação aprimorados para problemas de corte máximo e satisfatibilidade usando programação semidefinida, Journal of the ACM, Vol. 42, 1995, pp. 1115-1145); Michele Conforti , Gérard Cornuéjols e MR Rao (para Decomposição de matrizes balanceadas , Journal of Combinatorial Theory, Series B, Vol. 77, 1999, pp. 292-406).
  • 2003: JF Geelen , AMH Gerards e A. Kapoor (para The Excluded Minors for GF (4) -Representable Matroids, Journal of Combinatorial Theory Series B, Vol. 79, 2000, pp. 247-299); Bertrand Guenin (para A caracterização de grafos fracamente bipartidos, Journal of Combinatorial Theory Series B, Vol. 83, 2001, pp. 112-168); Satoru Iwata , Lisa Fleischer , Satoru Fujishige (para um algoritmo combinatorial fortemente polinomial para minimizar funções submodulares , Journal of the ACM, Vol. 48, 2001, pp. 761-777); Alexander Schrijver (para um algoritmo combinatório minimizando funções submodulares em tempo fortemente polinomial, Journal of Combinatorial Theory Series B, Vol. 80, 2000, pp. 346-355).
  • 2006: Manindra Agrawal , Neeraj Kayal e Nitin Saxena (por seu teste de número primo polinomial em "PRIMES is in P , Annals of Mathematics, Vol. 160, 2004, pp. 781-793); Mark Jerrum , Alistair Sinclair e Eric Vigoda ( para um algoritmo de aproximação de tempo polinomial para a permanente de uma matriz com entradas não negativas , Journal of the ACM, Vol. 51, 2004); Neil Robertson e Paul Seymour (para Graph Minors. XX. Conjectura de Wagner , Journal of Combinatorial Theory , Series B, Vol. 92, 2004, pp. 325-357).
  • 2009: Maria Chudnovsky , Neil Robertson , Paul Seymour , Robin Thomas (para o teorema do gráfico perfeito forte , Annals of Mathematics, Vol. 164, 2006, pp. 51-229); Daniel Spielman , Shang-Hua Teng (para Smoothed analysis of algorítmos: Por que o algoritmo simplex geralmente leva tempo polinomial , Journal of the ACM, Vol. 51, 2004, pp. 385-463); Thomas Hales (para uma prova da conjectura de Kepler , Annals of Mathematics, Vol. 162, 2005, pp. 1063-1183); Samuel P. Ferguson (para Sphere Packings, V.: Pentahedral Prisms , Discrete and Computational Geometry, Vol. 36, 2006, pp. 167-204).
  • 2012: Sanjeev Arora , Satish Rao e Umesh Vazirani (para fluxos Expander, embeddings geométricos e particionamento gráfico , Journal of the ACM, Vol. 56, pp. 1-37, 2009); Anders Johansson , Jeff Kahn e Van H. Vu (para Fatores em gráficos aleatórios , Random Structures and Algorithms Vol. 33, pp. 1-28, 2008); László Lovász e Balázs Szegedy (para Limites de sequências de grafos densos , Journal of Combinatorial Theory, Series B, Vol. 96, pp. 933–957, 2006)
  • 2015: Francisco Santos (para A Counterexample to the Hirsch Conjecture , Annals of Mathematics, 2012).
  • 2018: Peter Allen , Julia Böttcher , Simon Griffiths , Yoshiharu Kohayakawa , Robert Morris (para The cromática thresholds of graphs , Advances in Mathematics, Vol. 235, pp. 261–295, 2013); Thomas Rothvoss (para The Matching Polytope has Exponential Extension Complexity, Journal of the ACM, Vol. 64 pp. 1-19, 2017).
  • 2021: Béla Csaba , Daniela Kühn , Allan Lo , Deryk Osthus , Andrew Treglown : Prova da 1-fatoração e Conjecturas de Decomposição de Hamilton. In: Memoirs of the American Mathematical Society. 244, 2016, p. 0, doi : 10.1090 / memo / 1154 ; Jin-Yi Cai , XI Chen : Complexidade da contagem de CSP com pesos complexos. In: Journal of the ACM. 64, 2017, p. 1, doi : 10.1145 / 2822891 ; Ken-Ichi Kawarabayashi , Mikkel Thorup : Deterministic Edge Connectivity in Near-Linear Time. In: Journal of the ACM. 66, 2019, p. 1, doi : 10.1145 / 3274663 .

Links da web

  1. ↑ O Prêmio Fulkerson para trabalhos de destaque na área de matemática discreta é patrocinado conjuntamente por @math_opt e @amermathsoc. Em: twitter.com. 22 de julho de 2021, acessado em 24 de julho de 2021 .