富爾克森獎

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

參考資料

1. Mathematical Optimization Society. Mathematical Optimization Society. [2020-04-19]. （原始內容存檔於2019-02-12）.
2. Karp, Richard M. On the computational complexity of combinatorial problems. Networks. 1975, 5: 45–68. doi:10.1002/net.1975.5.1.45.
3. Appel, Kenneth; Haken, Wolfgang. Every planar map is four colorable, Part I: Discharging. Illinois Journal of Mathematics. 1977, 21: 429–490.
4. Seymour, Paul. The matroids with the max-flow min-cut property. Journal of Combinatorial Theory. 1977, 23: 189–222. doi:10.1016/0095-8956(77)90031-4.
5. Judin, D.B.; Nemirovski, Arkadi. Informational complexity and effective methods of solution for convex extremal problems. Ekonomika i Matematicheskie Metody. 1976, 12: 357–369.
6. Khachiyan, Leonid. A polynomial algorithm in linear programming. Akademiia Nauk SSSR. Doklady. 1979, 244: 1093–1096.
7. Leonid Khachiyan, professor, leading computer scientist, Boston Globe, May 5, 2005 [2020-04-19], （原始內容存檔於2016-03-03）.
8. Grötschel, Martin; Lovász, László; Schrijver, Alexander. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica. 1981, 1: 169–197. doi:10.1007/bf02579273.
9. Egorychev, G. P. The solution of van der Waerden's problem for permanents. Akademiia Nauk SSSR. Doklady. 1981, 258: 1041–1044.
10. Falikman, D. I. A proof of the van der Waerden conjecture on the permanent of a doubly stochastic matrix. Matematicheskie Zametki. 1981, 29: 931–938.
11. Beck, Jozsef. Roth's estimate of the discrepancy of integer sequences is nearly sharp. Combinatorica. 1981, 1 (4): 319–325. doi:10.1007/bf02579452.
12. Lenstra, H. W.; Jr. Integer programming with a fixed number of variables. Mathematics of Operations Research. 1983, 8 (4): 538–548. doi:10.1287/moor.8.4.538.
13. Luks, Eugene M. Isomorphism of graphs of bounded valence can be tested in polynomial time. Journal of Computer and System Sciences. 1982, 25 (1): 42–65. doi:10.1016/0022-0000(82)90009-5.
14. U of O Computer Chief Gets Top Award, Eugene Register-Guard, August 10, 1985 [2020-04-19], （原始內容存檔於2021-12-07）.
15. Tardos, Éva. A strongly polynomial minimum cost circulation algorithm. Combinatorica. 1985, 5: 247–256. doi:10.1007/bf02579369.
16. Karmarkar, Narendra. A new polynomial-time algorithm for linear programming. Combinatorica. 1984, 4: 373–395. doi:10.1007/bf02579150.
17. Dyer, Martin E.; Frieze, Alan M.; Kannan, Ravindran. A random polynomial time algorithm for approximating the volume of convex bodies. Journal of the ACM. 1991, 38 (1): 1–17. doi:10.1145/102782.102783.
18. Alfred Lehman, "The width-length inequality and degenerate projective planes," W. Cook and P. D. Seymour (eds.), Polyhedral Combinatorics, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, volume 1, (American Mathematical Society, 1990) pp. 101-105.
19. Nikolai E. Mnev, "The universality theorems on the classification problem of configuration varieties and convex polytope varieties," O. Ya. Viro (ed.), Topology and Geometry-Rohlin Seminar, Lecture Notes in Mathematics 1346 (Springer-Verlag, Berlin, 1988) pp. 527-544.
20. Billera, Louis. Homology of smooth splines: Generic triangulations and a conjecture of Strang. Transactions of the American Mathematical Society. 1988, 310: 325–340. doi:10.2307/2001125.
21. Kalai, Gil. Upper bounds for the diameter and height of graphs of the convex polyhedra. Discrete and Computational Geometry. 1992, 8: 363–372. doi:10.1007/bf02293053.
22. Robertson, Neil; Seymour, Paul; Thomas, Robin. Hadwiger's conjecture for K_6-free graphs. Combinatorica. 1993, 13: 279–361. doi:10.1007/bf01202354.
23. Kim, Jeong Han, The Ramsey number R(3,t) has order of magnitude t²/log t, Random Structures & Algorithms, 1995, 7 (3): 173–207, MR 1369063, doi:10.1002/rsa.3240070302.
24. Goemans, Michel X.; Williamson, David P. Improved approximation algorithms for the maximum cut and satisfiability probelsm using semi-definite programming. Journal of the ACM. 1995, 42 (6): 1115–1145. doi:10.1145/227683.227684.
25. Michele Conforti, Gérard Cornuéjols, and M. R. Rao, "Decomposition of balanced matrices", Journal of Combinatorial Theory, Series B, 77 (2): 292–406, 1999.
26. MR Rao New Dean Of ISB, Financial Express, July 2, 2004 [2020-04-19], （原始內容存檔於2022-03-19）.
27. J. F. Geelen, A. M. H. Gerards and A. Kapoor, "The Excluded Minors for GF(4)-Representable Matroids," Journal of Combinatorial Theory, Series B, 79 (2): 247–2999, 2000.
28. 2003 Fulkerson Prize citation （頁面存檔備份，存於互聯網檔案館）, retrieved 2012-08-18.
29. Bertrand Guenin, "A characterization of weakly bipartite graphs," Journal of Combinatorial Theory, Series B, 83 (1): 112–168, 2001.
30. Satoru Iwata, Lisa Fleischer, Satoru Fujishige, "A combinatorial strongly polynomial algorithm for minimizing submodular functions," Journal of the ACM, 48 (4): 761–777, 2001.
31. Alexander Schrijver, "A combinatorial algorithm minimizing submodular functions in strongly polynomial time," Journal of Combinatorial Theory, Series B 80 (2): 346–355, 2000.
32. Manindra Agrawal, Neeraj Kayal and Nitin Saxena, "PRIMES is in P," Annals of Mathematics, 160 (2): 781–793, 2004.
33. Raghunathan, M. S., India as a player in Mathematics, The Hindu, June 11, 2009 [2020-04-19], （原始內容存檔於2009-06-14）.
34. 2006 Fulkerson Prize citation （頁面存檔備份，存於互聯網檔案館）, retrieved 2012-08-19.
35. Mark Jerrum, Alistair Sinclair and Eric Vigoda, "A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries," Journal of the ACM, 51 (4): 671–697, 2004.
36. Neil Robertson and Paul Seymour, "Graph Minors. XX. Wagner's conjecture," Journal of Combinatorial Theory, Series B, 92 (2): 325–357, 2004.
37. Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin. The strong perfect graph theorem. Annals of Mathematics. 2006, 164: 51–229. arXiv:math/0212070 . doi:10.4007/annals.2006.164.51.
38. 2009 Fulkerson Prize citation （頁面存檔備份，存於互聯網檔案館）, retrieved 2012-08-19.
39. Spielman, Daniel A.; Teng, Shang-Hua. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. Journal of the ACM. 2004, 51: 385–463. arXiv:math/0212413 . doi:10.1145/990308.990310.
40. Hales, Thomas C. A proof of the Kepler conjecture. Annals of Mathematics. 2005, 162: 1063–1183.
41. Ferguson, Samuel P. Sphere Packings, V. Pentahedral Prisms. Discrete and Computational Geometry. 2006, 36: 167–204. doi:10.1007/s00454-005-1214-y.
42. Arora, Sanjeev; Rao, Satish; Vazirani, Umesh. Expander flows, geometric embeddings and graph partitioning. Journal of the ACM. 2009, 56: 1–37. doi:10.1145/1502793.1502794.
43. Johansson, Anders; Kahn, Jeff; Vu, Van H. Factors in random graphs. Random Structures and Algorithms. 2008, 33: 1–28. doi:10.1002/rsa.20224.
44. Lovász, László; Szegedy, Balázs. Limits of dense graph sequences. Journal of Combinatorial Theory. 2006, 96: 933–957. arXiv:math/0408173 . doi:10.1016/j.jctb.2006.05.002.
45. Santos, Francisco, A counterexample to the Hirsch conjecture, Annals of Mathematics, 2011, 176 (1): 383–412, MR 2925387, arXiv:1006.2814 , doi:10.4007/annals.2012.176.1.7
46. 2015 Fulkerson Prize citation （頁面存檔備份，存於互聯網檔案館）, retrieved 2015-07-18.

外部連結

• 官方網站（頁面存檔備份，存於互聯網檔案館） (MOS)
• 有詳細介紹的官方網站（頁面存檔備份，存於互聯網檔案館） (AMS website)