풀커슨상

델버트 레이 풀커슨 상()은 이산수학 분야에서 뛰어난 논문에 주어지는 상이다.

 역사 
풀커슨 상은 1979년에 미국의 수학자 델버트 레이 풀커슨(, 1924년 8월 14일~1976년 1월 10일)을 기리기 위하여 창설되었고, 이후 3년마다 수여되고 있다. 미국 수학회와 수리최적화학회()에서 공동으로 수여한다. 한 번에 최대 3개의 논문까지 수여될 수 있으며, 각 논문의 공저자의 수는 제한이 없다.

상금은 원래 750 미국 달러였으나, 1994년에 1500 미국 달러로 증가하였다.

 수상자 
 연도  수상자  논문 1979  리처드 매닝 카프() Richard M. Karp, "On the computational complexity of combinatorial problems", Networks 5: 45–68, 1975. 케네스 아펠, 볼프강 하켄() Kenneth Appel and Wolfgang Haken, "Every planar map is four colorable, Part I: Discharging," Illinois Journal of Mathematics 21: 429–490, 1977 폴 시모어() Paul Seymour, "The matroids with the max-flow min-cut property," Journal of Combinatorial Theory, Series B, 23: 189–222, 1977. 1982  다비트 보리소비치 유딘(), 아르카디 세묘노비치 네미롭스키(), 레오니트 겐리호비치 하치얀(, ), 마르틴 그뢰첼(), 로바스 라슬로, 알렉산더르 스흐레이버르() D.B. Judin and Arkadi Nemirovski, "Informational complexity and effective methods of solution for convex extremal problems," Ekonomika i Matematicheskie Metody 12: 357–369, 1976.Leonid Khachiyan, "A polynomial algorithm in linear programming," Akademiia Nauk SSSR. Doklady 244: 1093–1096, 1979.Martin Grötschel, László Lovász and Alexander Schrijver, "The ellipsoid method and its consequences in combinatorial optimization," Combinatorica 1: 169–197, 1981. 게오르기 페트로비치 예고리체프(), 드미트리 이힐로비치 팔리크만() G. P. Egorychev, "The solution of van der Waerden's problem for permanents," Akademiia Nauk SSSR. Doklady 258: 1041–1044, 1981.D. I. Falikman, "A proof of the van der Waerden conjecture on the permanent of a doubly stochastic matrix," Matematicheskie Zametki 29: 931–938, 1981. 1985  베크 요제프() Jozsef Beck, "Roth's estimate of the discrepancy of integer sequences is nearly sharp," Combinatorica 1 (4): 319–325, 1981. 헨드릭 빌럼 렌스트라 2세() H. W. Lenstra, Jr., "Integer programming with a fixed number of variables," Mathematics of Operations Research 8 (4): 538–548, 1983.  유진 마이클 럭스() Eugene M. Luks, "Isomorphism of graphs of bounded valence can be tested in polynomial time," Journal of Computer and System Sciences 25 (1): 42–65, 1982. 1988  터르도시 에버() Éva Tardos, "A strongly polynomial minimum cost circulation algorithm," Combinatorica 5: 247-256, 1985. 나렌드라 크리슈나 카르마르카르(Narendra Krishna Karmarkar) Narendra Karmarkar, "A new polynomial-time algorithm for linear programming," Combinatorica 4:373–395, 1984.1991  마틴 다이어(), 앨런 프리즈(), 라빈드란 칸난(Ravindran Kannan) Martin E. Dyer, Alan M. Frieze and Ravindran Kannan, "A random polynomial time algorithm for approximating the volume of convex bodies", Journal of the Association for Computing Machinery 38 (1): 1–17, 1991. 앨프리드 리먼() 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. 니콜라이 예브게니예비치 므뇨프() 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. 1994  루이스 빌레라() Louis Billera, "Homology of smooth splines: Generic triangulations and a conjecture of Strang", Transactions of the AMS 310: 325–340, 1988. 길 칼라이() Gil Kalai, "Upper bounds for the diameter and height of graphs of the convex polyhedra", Discrete and Computational Geometry 8: 363–372, 1992. 닐 로버트슨(), 폴 시모어(), 로빈 토머스() Neil Robertson, Paul Seymour and Robin Thomas, "Hadwiger's conjecture for -free graphs," Combinatorica 13: 279–361, 1993. 1997  김정한 Jeong Han Kim, "The Ramsey Number R(3,t) Has Order of Magnitude t^2/log t," Random Structures and Algorithms 7 (3): 173–207, 1995. 2000  미셸 그자비에 괴망(), 데이비드 윌리엄슨() Michel X. Goemans and David P. Williamson, "Improved approximation algorithms for the maximum cut and satisfiability probelsm using semi-definite programming", Journal of the Association for Computing Machinery 42 (6): 1115–1145, 1995. 미켈란젤로 콘포르티(), 제라르 피에르 코르뉘에졸(), 멘두 람모한 라오(Mendu Rammohan Rao) 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. 2003  제임스 길런(), 알버르트 헤라르츠(), 아자이 카푸르(Ajai Kapoor) 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. 버트런드 게닌() Bertrand Guenin, "A characterization of weakly bipartite graphs," Journal of Combinatorial Theory, Series B, 83 (1): 112–168, 2001. 이와타 사토루(), Lisa Fleischer, 후지시게 사토루(),  알렉산더르 스흐레이버르() Satoru Iwata, Lisa Fleischer, Satoru Fujishige, "A combinatorial strongly polynomial algorithm for minimizing submodular functions," Journal of the ACM, 48 (4): 761–777, 2001.Alexander Schrijver, "A combinatorial algorithm minimizing submodular functions in strongly polynomial time," Journal of Combinatorial Theory, Series B 80 (2): 346–355, 2000. 2006  마닌드라 아가르왈(Manindra Agarwal), 니라지 카얄(Neeraj Kayal), 니틴 삭세나(Nitin Saxena) Manindra Agrawal, Neeraj Kayal and Nitin Saxena, "PRIMES is in P," Annals of Mathematics, 160 (2): 781–793, 2004. 마크 제럼(), 앨리스터 싱클레어(), 에릭 비고다() 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. 닐 로버트슨(), 폴 시모어() Neil Robertson and Paul Seymour,  "Graph Minors. XX. Wagner's conjecture," Journal of Combinatorial Theory, Series B, 92 (2): 325–357, 2004. 2009  마리아 추드노브스키(, ),  닐 로버트슨(), 폴 시모어(), 로빈 토머스() Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas, "The strong perfect graph theorem", Annals of Mathematics, 164: 51–229, 2006. 대니얼 앨런 스필먼(), 텅샹화() Daniel A. Spielman and Shang-Hua Teng, "Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time", Journal of the ACM 51: 385–463, 2004. 토머스 캘리스터 헤일스(), 새뮤얼 퍼구슨() Thomas C. Hales, "A proof of the Kepler conjecture", Annals of Mathematics 162: 1063–1183, 2005.Samuel P. Ferguson, "Sphere Packings, V. Pentahedral Prisms", Discrete and Computational Geometry 36: 167–204, 2006.2012  산지브 아로라(Sanjeev Arora), 사티시 라오(Satish Rao), 우메시 바지라니(Umesh Vazirani) Sanjeev Arora, Satish Rao, and Umesh Vazirani, "Expander flows, geometric embeddings and graph partitioning", Journal of the ACM 56: 1-37, 2009. 안데르스 요한손(), 제프 칸(), 부하반() Anders Johansson, Jeff Kahn, and Van H. Vu, "Factors in random graphs", Random Structures and Algorithms 33: 1-28, 2008. 로바스 라슬로, 세게디 벌라주() László Lovász and Balázs Szegedy, "Limits of dense graph sequences", Journal of Combinatorial Theory, Series B, 96: 933-957, 2006.

 각주 

 외부 링크 
  (수리최적화학회 웹사이트)
  (미국 수학회 웹사이트)

분류:수학상
분류:미국의 과학기술상
분류:3년마다 열리는 행사