富尔克森奖

富尔克森奖（英语：Fulkerson Prize）是国际数学优化学会（英语：Mathematical Optimization Society）和美国数学学会联合设立的奖项，专门奖励离散数学领域的杰出论文。在国际数学优化学会每三年召开一次的大会上奖励至多三篇论文，奖金各1500美元。最初奖金来自于一个纪念基金。此纪念基金是由数学家戴尔伯特·雷·富尔克森（英语：Delbert Ray Fulkerson）的朋友们建立的、美国数学学会管理，用于激励富尔克森自己研究领域的杰出数学成果。目前奖金来自于国际数学优化学会管理的一笔捐赠资产。

富尔克森奖
授予对象	离散数学领域的杰出论文
国家／地区	美国
主办单位	国际数学优化学会（英语：Mathematical Optimization Society） 美国数学学会
奖励	1500美元
首次颁发	1979年
官方网站	http://www.ams.org/profession/prizes-awards/ams-prizes/fulkerson-prize

获奖论文

^[1]

• 1979年:
  • 理查德·卡普 - 对很多重要的NP完全问题进行分类。^[2]
  • 凯尼斯·阿佩尔和沃夫冈·哈肯 - 四色定理。^[3]
  • Paul Seymour（英语：Paul Seymour (mathematician)） - 把最大流最小割定理推广到拟阵。^[4]
• 1982:
  • D.B. Judin, 阿尔卡迪·内米罗夫斯基, Leonid Khachiyan（英语：Leonid Khachiyan）, Martin Grötschel（英语：Martin Grötschel）, 洛瓦兹·拉兹洛 和 Alexander Schrijver（英语：Alexander Schrijver） - 线性规划和组合优化中的椭球方法（英语：ellipsoid method）。^{[5][6] [7] [8]}
  • G. P. Egorychev（英语：Georgy Petrovich Egorychev）和D. I. Falikman - 证明范德瓦尔登的猜想：所有元素都相等的矩阵在所有双随机矩阵（英语：Doubly stochastic matrix）中有着最小的积和式。^[9][10]
• 1985:
  • Jozsef Beck（英语：Jozsef Beck） - 等差数列的差异（英语：discrepancy theory）的紧界。^[11]
  • 亨德里克·伦斯特拉 - 应用几何数论在约束个数的多项式时间内求解变元数较少的整数规划问题。^[12]
  • Eugene M. Luks（英语：Eugene M. Luks） - 对于最大度有上界的图求解图同构问题的多项式时间算法。^[13][14]
• 1988:
  • 爱娃·塔多斯 - 在强多项式时间内求解网络中的最小费用环流。^[15]
  • Narendra Karmarkar（英语：Narendra Karmarkar） - 线性规划中的Karmarkar算法（英语：Karmarkar's algorithm）。^[16]
• 1991:
  • Martin E. Dyer, Alan M. Frieze 和 Ravindran Kannan - 基于随机游走的计算凸体体积的近似算法。^[17]
  • Alfred Lehman - 关于逻辑矩阵的完美图理论。^[18]
  • Nikolai E. Mnev - Mnev通用定理（英语：Mnev's universality theorem）：每个半代数集（英语：Semialgebraic set）都等价于一个定向拟阵的所有实现构成的空间。^[19]
• 1994:
  • Louis Billera（英语：Louis Billera） - 求出空间三角剖分（英语：Triangulation_(geometry)）上的分段多项式函数空间的基。^[20]
  • Gil Kalai（英语：Gil Kalai） - 在Hirsch猜想（英语：Hirsch conjecture）上的进展。^[21]
  • Neil Robertson（英语：Neil Robertson (mathematician)）, Paul Seymour（英语：Paul Seymour (mathematician)）和罗宾·托马斯 - 哈德维格猜想（英语：Hadwiger conjecture (graph theory)）的6色情形。^[22]
• 1997:
  • Jeong Han Kim（英语：Jeong Han Kim） - 求出拉姆齐数R(3,t)的渐进增长率。^[23]
• 2000:
  • Michel X. Goemans（英语：Michel Goemans）和David P. Williamson（英语：David P. Williamson） - 基于半正定规划的近似算法。^[24]
  • Michele Conforti, Gérard Cornuéjols（英语：Gérard Cornuéjols）和Mendu Rammohan Rao（英语：Mendu Rammohan Rao） - 在多项式时间内识别平衡逻辑矩阵（英语：Balanced matrix）的算法。^[25][26]
• 2003:
  • Jim Geelen（英语：Jim Geelen）, A. M. H. Gerards 和 A. Kapoor - 关于拟阵子式（英语：matroid minor）的Rota猜想（英语：Rota's conjecture）在GF(4)的情形。^[27][28]
  • Bertrand Guenin - 弱二部图的一个禁止子图刻画（英语：Forbidden graph characterization）。^[29][28]
  • Satoru Iwata, Lisa Fleischer, Satoru Fujishige和Alexander Schrijver（英语：Alexander Schrijver） - 证明次模函数最小化问题（英语：Submodular_set_function#Optimization_problems）是强多项式时间的。^[30][31][28]
• 2006:
  • Manindra Agrawal（英语：Manindra Agrawal）, Neeraj Kayal（英语：Neeraj Kayal） 和 Nitin Saxena（英语：Nitin Saxena） - AKS质数测试.^[32][33][34]
  • Mark Jerrum（英语：Mark Jerrum）, 阿利斯泰尔·辛克莱尔 和 Eric Vigoda - 对积和式的近似计算。^[35][34]
  • Neil Robertson（英语：Neil Robertson (mathematician)） 和 Paul Seymour（英语：Paul Seymour (mathematician)） - Robertson-Seymour定理（英语：Robertson–Seymour theorem）。.^[36][34]
• 2009:
  • Maria Chudnovsky（英语：Maria Chudnovsky）, Neil Robertson, Paul Seymour 和 罗宾·托马斯 - 强完美图定理（英语：strong perfect graph theorem）。^[37][38]
  • Daniel A. Spielman（英语：Daniel A. Spielman） 和 滕尚华 - 线性规划算法的光滑分析（英语：smoothed analysis）。^[39][38]
  • 托马斯·黑尔斯 和 Samuel P. Ferguson - 证明关于最密堆积的开普勒猜想。^[40][41][38]
• 2012:
  • Sanjeev Arora（英语：Sanjeev Arora）, Satish Rao 和 乌梅什·瓦兹拉尼 - 把图的顶点割（英语：Vertex_separator）和相关问题的近似比例从${\displaystyle O(\log n)}$改进到${\displaystyle O({\sqrt {\log n}})}$。^[42]
  • Anders Johansson, Jeff Kahn（英语：Jeff Kahn） 和 Van H. Vu（英语：Van H. Vu） - 确定了随机图具有下述性质的边密度的阈值：能被同构于一个给定的更小图的图的不交并覆盖。^[43]
  • 洛瓦兹·拉兹洛和Balázs Szegedy（英语：Balázs Szegedy） - 刻画稠密图（英语：dense graph）序列的子图的重数。^[44]
• 2015 :
  • Francisco Santos Leal（英语：Francisco Santos Leal） - 举出Hirsch猜想（英语：Hirsch conjecture）的一个反例。^[45][46]
• 2018 :
  • Robert Morris（英语：Robert Morris (mathematician)）, 小早川美晴（英语：Yoshiharu Kohayakawa）, Simon Griffiths, Peter Allen 和 Julia Böttcher - The chromatic thresholds of graphs
  • Thomas Rothvoss - The Matching Polytope has Exponential Extension Complexity