Giải Fulkerson

Giải Fulkerson
Trao cho	Outstanding papers in the area of Toán học rời rạc
Quốc gia	Hoa Kỳ
Được trao bởi	Mathematical Optimization Society Hội Toán học Hoa Kỳ
Phần thưởng	$1.500
Lần đầu tiên	1979

Giải Fulkerson là một giải thưởng dành cho các bài báo xuất sắc về Toán học rời rạc do Hội Quy Hoạch Toán học (Mathematical Programming Society) và Hội Toán học Hoa Kỳ cùng bảo trợ. Giải thưởng bắt đầu từ năm 1979. Hiện nay, cứ 3 năm 1 lần, tại "Hội nghị quốc tế" của "Hội Quy Hoạch Toán học", có 3 giải được trao, mỗi giải trị giá 1500$. Ban đầu, các giải được tài trợ bởi quỹ tưởng niệm do bạn bè của Delbert Ray Fulkerson đóng góp và do "Hội Toán học Hoa Kỳ" quản lý.

Thuật ngữ toán rời rạc ở đây được hiểu là bao gồm lý thuyết đồ thị, mạng, tối ưu toán học, tổ hợp ứng dụng và các vấn đề liên quan. Trong khi các nghiên cứu trong lĩnh vực này thường liên quan đến ứng dụng thực tế, việc quyết định các bài báo được giải lại dựa trên chất lượng và ý nghĩa về mặt toán học của chúng.

Paul Seymour, nhà toán học nổi tiếng làm việc trong lĩnh vực lý thuyết đồ thị, là người duy nhất 4 lần được nhận giải thưởng này (vào các năm 1979, 1994, 2006, 2009).

Các người đoạt giải

• 1979: Richard M. Karp; Kenneth Appel và Wolfgang Haken; Paul Seymour.
• 1982: D.B. Judin và A.S. Nemirovskii; Leonid Khachiyan; G. P. Egorychev; D.I. Falikman; Martin Grötschel, László Lovász và Alexander Schrijver.
• 1985: Jozsef Beck; H. W. Lenstra, Jr.; Eugene M. Luks.
• 1988: Éva Tardos; Narendra Karmarkar.
• 1991: Martin E. Dyer, Alan M. Frieze và Ravindran Kannan; Alfred Lehman; Nikolai E. Mnev.
• 1994: Louis Billera; Gil Kalai; Neil Robertson, Paul Seymour và Robin Thomas.
• 1997: Jeong Han Kim.
• 2000: Michel X. Goemans và David P. Williamson; Michele Conforti và Gerard Cornuejols và M. R. Rao.
• 2003: J. F. Geelen, A. M. H. Gerards và A. Kapoor; Bertrand Guenin; Satoru Iwata, Lisa Fleischer, Satoru Fujishige; Alexander Schrijver.
• 2006: Manindra Agarwal, Neeraj Kayal và Nitin Saxena; Mark Jerrum, Alistair Sinclair và Eric Vigoda; Neil Robertson và Paul Seymour.
• 2009:
  • Maria Chudnovsky, Neil Robertson, Paul Seymour, và Robin Thomas, cho "The strong perfect graph theorem", Annals of Mathematics, 164 (2006) 51–229.
  • Daniel A. Spielman và Shang-Hua Teng, cho "Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time", Journal of the ACM 51 (2004) 385–463.
  • Thomas C. Hales, cho "A proof of the Kepler conjecture", Annals of Mathematics 162 (2005) 1063–1183
  • Samuel P. Ferguson, cho "Sphere Packings, V. Pentahedral Prisms", Discrete and Computational Geometry 36 (2006) 167–204.
• 2012:
  • Sanjeev Arora, Satish Rao, và Umesh Vazirani cho việc làm giảm tỉ lệ xấp xỉ cho bài toán chia đồ thị và các bài toán liên quan từ ${\displaystyle O(\log n)}$ xuống ${\displaystyle O({\sqrt {\log n}})}$.^[1]
  • Anders Johansson, Jeff Kahn và Vũ Hà Văn cho việc xác định ngưỡng của mật độ cạnh sao cho ở trên ngưỡng đó, một đồ thị ngẫu nhiên có thể được phủ bằng các bản sao không giao nhau của một đồ thị nhỏ hơn cho trước.^[2]
  • László Lovász và Balázs Szegedy cho việc xác định tính chất quyết định số lần xuất hiện của đồ thị con trong một dãy các đồ thị dày đặc.^[3]

Tham khảo

1. Sanjeev Arora, Satish Rao, and Umesh Vazirani, "Expander flows, geometric embeddings and graph partitioning", Journal of the ACM 56: 1-37, 2009.
2. Anders Johansson, Jeff Kahn, and Vũ Hà Văn, "Factors in random graphs", Random Structures and Algorithms 33: 1-28, 2008. doi:10.1002/rsa.20224
3. László Lovász and Balázs Szegedy, "Limits of dense graph sequences", Journal of Combinatorial Theory, Series B, 96: 933-957, 2006.

Liên kết ngoài

• Trang mạng chính thức của giải thưởng