富爾克森獎

富爾克森獎（英語：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