풀커슨상 문서 원본 보기

'''델버트 레이 풀커슨 상'''({{llang|en|Delbert Ray Fulkerson Prize}})은 [[이산수학]] 분야에서 뛰어난 논문에 주어지는 상이다.

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

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

== 수상자 ==
{| class=wikitable
! 연도 !! 수상자 !! 논문
|-
| rowspan=3 | 1979 || 리처드 매닝 카프({{llang|en|Richard Manning Karp}}) ||<ref>Richard M. Karp, "On the computational complexity of combinatorial problems", ''Networks'' 5: 45–68, 1975.</ref>
|-
| [[케네스 아펠]], 볼프강 하켄({{llang|de|Wolfgang Haken}}) ||<ref>Kenneth Appel and Wolfgang Haken, "Every planar map is four colorable, Part I: Discharging," ''Illinois Journal of Mathematics'' 21: 429–490, 1977</ref>
|-
| 폴 시모어({{llang|en|Paul Seymour}}) ||<ref>Paul Seymour, "The matroids with the max-flow min-cut property," ''[[Journal of Combinatorial Theory]]'', Series B, 23: 189–222, 1977.</ref>
|-
|rowspan=2| 1982 || 다비트 보리소비치 유딘({{llang|ru|Давид Борисович Юдин}}), 아르카디 세묘노비치 네미롭스키({{llang|ru|Аркадий Семёнович Немиро́вский}}), 레오니트 겐리호비치 하치얀({{llang|ru|Леонид Генрихович Хачиян}}, {{llang|hy|Լեոնիդ Գենրիխովիչ Խաչիյան}}), 마르틴 그뢰첼({{llang|de|Martin Grötschel}}), [[로바스 라슬로]], 알렉산더르 스흐레이버르({{llang|nl|Alexander Schrijver}}) ||<ref>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.</ref><ref>[[Leonid Khachiyan]], "A polynomial algorithm in linear programming," ''Akademiia Nauk SSSR. Doklady'' 244: 1093–1096, 1979.</ref><ref>Martin Grötschel, [[László Lovász]] and [[Alexander Schrijver]], "The ellipsoid method and its consequences in combinatorial optimization," ''Combinatorica'' 1: 169–197, 1981.</ref>
|-
| 게오르기 페트로비치 예고리체프({{llang|ru|Георгий Петрович  Его́рычев}}), 드미트리 이힐로비치 팔리크만({{llang|ru|Дмитрий Ихилович Фаликман}}) ||<ref>G. P. Egorychev, "The solution of van der Waerden's problem for permanents," ''Akademiia Nauk SSSR. Doklady'' 258: 1041–1044, 1981.</ref><ref>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.</ref>
|-
|rowspan=3| 1985 || 베크 요제프({{llang|hu|Beck József}}) ||<ref>[[Jozsef Beck]], "Roth's estimate of the discrepancy of integer sequences is nearly sharp," ''Combinatorica'' 1 (4): 319–325, 1981.</ref>
|-
| 헨드릭 빌럼 렌스트라 2세({{llang|nl|Hendrik Willem Lenstra, Jr}}) ||<ref>H. W. Lenstra, Jr., "Integer programming with a fixed number of variables," ''Mathematics of Operations Research'' 8 (4): 538–548, 1983.</ref>
|-
|  유진 마이클 럭스({{llang|en|Eugene Michael Luks}}) ||<ref>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.</ref>
|-
| rowspan=2 | 1988 || 터르도시 에버({{llang|hu|Tardos Éva}}) ||<ref>[[Éva Tardos]], "A strongly polynomial minimum cost circulation algorithm," ''Combinatorica'' 5: 247-256, 1985.</ref>
|-
| 나렌드라 크리슈나 카르마르카르(Narendra Krishna Karmarkar) ||<ref>[[Narendra Karmarkar]], "A new polynomial-time algorithm for linear programming," ''Combinatorica'' 4:373–395, 1984.</ref>
|-
| rowspan=3 |1991 || 마틴 다이어({{llang|en|Martin E. Dyer}}), 앨런 프리즈({{llang|en|Alan M. Frieze}}), 라빈드란 칸난(Ravindran Kannan) ||<ref>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.</ref>
|-
| 앨프리드 리먼({{llang|en|Alfred Lehman}}) ||<ref>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.</ref>
|-
| 니콜라이 예브게니예비치 므뇨프({{llang|ru|Николай Евгеньевич Мнёв}}) ||<ref>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.</ref>
|-
| rowspan=3 | 1994 || 루이스 빌레라({{llang|en|Louis J. Billera}}) ||<ref>Louis Billera, "Homology of smooth splines: Generic triangulations and a conjecture of Strang", ''Transactions of the AMS'' 310: 325–340, 1988.</ref>
|-
| 길 칼라이({{Llang|he|גיל קלעי}}) ||<ref>Gil Kalai, "Upper bounds for the diameter and height of graphs of the convex polyhedra", ''[[Discrete and Computational Geometry]]'' 8: 363–372, 1992.</ref>
|-
| 닐 로버트슨({{llang|en|Neil Robertson}}), 폴 시모어({{llang|en|Paul Seymour}}), 로빈 토머스({{llang|en|Robin Thomas}}) ||<ref>[[Neil Robertson (mathematician)|Neil Robertson]], [[Paul Seymour (mathematician)|Paul Seymour]] and [[Robin Thomas (mathematician)|Robin Thomas]], "Hadwiger's conjecture for <math>K_6</math>-free graphs," ''Combinatorica'' 13: 279–361, 1993.</ref>
|-
| 1997 || [[김정한 (수학자)|김정한]] ||<ref>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.</ref>
|-
| rowspan=2 | 2000 || 미셸 그자비에 괴망({{llang|fr|Michel Xavier Goemans}}), 데이비드 윌리엄슨({{llang|en|David P. Williamson}}) ||<ref>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.</ref>
|-
| 미켈란젤로 콘포르티({{llang|it|Michelangelo Conforti}}), 제라르 피에르 코르뉘에졸({{llang|fr|Gérard Pierre Cornuéjols}}), 멘두 람모한 라오(Mendu Rammohan Rao) ||<ref>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.</ref>
|-
| rowspan=3 | 2003 || 제임스 길런({{llang|en|James F. Geelen}}), 알버르트 헤라르츠({{llang|nl|Albert M. H. Gerards}}), 아자이 카푸르(Ajai Kapoor) ||<ref>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.</ref>
|-
| 버트런드 게닌({{llang|en|Bertrand Guenin}}) ||<ref>Bertrand Guenin, "A characterization of weakly bipartite graphs," ''[[Journal of Combinatorial Theory]]'', Series B, 83 (1): 112–168, 2001.</ref>
|-
| 이와타 사토루({{llang|ja|岩田 覚}}), Lisa Fleischer, 후지시게 사토루({{llang|ja|藤重 悟}}),  알렉산더르 스흐레이버르({{llang|nl|Alexander Schrijver}}) ||<ref>Satoru Iwata, Lisa Fleischer, Satoru Fujishige, "A combinatorial strongly polynomial algorithm for minimizing submodular functions," ''[[Journal of the ACM]]'', 48 (4): 761–777, 2001.</ref><ref>[[Alexander Schrijver]], "A combinatorial algorithm minimizing submodular functions in strongly polynomial time," ''[[Journal of Combinatorial Theory]]'', Series B 80 (2): 346–355, 2000.</ref>
|-
| rowspan=3 | 2006 || 마닌드라 아가르왈(Manindra Agarwal), 니라지 카얄(Neeraj Kayal), 니틴 삭세나(Nitin Saxena) ||<ref>Manindra Agrawal, Neeraj Kayal and Nitin Saxena, "PRIMES is in P," ''[[Annals of Mathematics]]'', 160 (2): 781–793, 2004.</ref>
|-
| 마크 제럼({{llang|en|Mark Jerrum}}), 앨리스터 싱클레어({{llang|en|Alistair Sinclair}}), 에릭 비고다({{llang|en|Eric Vigoda}}) ||<ref>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.</ref>
|-
| 닐 로버트슨({{llang|en|Neil Robertson}}), 폴 시모어({{llang|en|Paul Seymour}}) ||<ref>Neil Robertson and Paul Seymour,  "Graph Minors. XX. Wagner's conjecture," ''Journal of Combinatorial Theory'', Series B, 92 (2): 325–357, 2004.</ref>
|-
| rowspan=3| 2009 || 마리아 추드노브스키({{llang|en|Maria Chudnovsky}}, {{llang|he|מריה צ'ודנובסקי}}),  닐 로버트슨({{llang|en|Neil Robertson}}), 폴 시모어({{llang|en|Paul Seymour}}), 로빈 토머스({{llang|en|Robin Thomas}}) ||<ref>Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas, "The strong perfect graph theorem", ''Annals of Mathematics'', 164: 51–229, 2006.</ref>
|-
| 대니얼 앨런 스필먼({{llang|en|Daniel Alan Spielman}}), 텅샹화({{zh|s=滕尚华|t=滕尚華|p=Téng Shànghuá}}) ||<ref>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.</ref>
|-
| 토머스 캘리스터 헤일스({{llang|en|Thomas Callister Hales}}), 새뮤얼 퍼구슨({{llang|en|Samuel P. Ferguson}}) ||<ref>Thomas C. Hales, "A proof of the Kepler conjecture", ''Annals of Mathematics'' 162: 1063–1183, 2005.</ref><ref>Samuel P. Ferguson, "Sphere Packings, V. Pentahedral Prisms", ''Discrete and Computational Geometry'' 36: 167–204, 2006.</ref>
|-
| rowspan=3 |2012 || 산지브 아로라(Sanjeev Arora), 사티시 라오(Satish Rao), 우메시 바지라니(Umesh Vazirani) ||<ref>Sanjeev Arora, Satish Rao, and Umesh Vazirani, "Expander flows, geometric embeddings and graph partitioning", ''Journal of the ACM'' 56: 1-37, 2009.</ref>
|-
| 안데르스 요한손({{llang|sv|Anders Johansson}}), 제프 칸({{llang|en|Jeff Kahn}}), 부하반({{llang|vi|Vũ Hà Văn}}) ||<ref>Anders Johansson, Jeff Kahn, and Van H. Vu, "Factors in random graphs", ''Random Structures and Algorithms'' 33: 1-28, 2008.</ref>
|-
| [[로바스 라슬로]], 세게디 벌라주({{llang|hu|Szegedy Balázs}}) ||<ref>László Lovász and Balázs Szegedy, "Limits of dense graph sequences", ''Journal of Combinatorial Theory'', Series B, 96: 933-957, 2006.</ref>
|}

== 각주 ==
{{각주|25em}}

== 외부 링크 ==
* {{웹 인용|url=http://www.mathopt.org/?nav=fulkerson|제목=The Fulkerson Prize|출판사=Mathematical Optimization Society|언어=en}} (수리최적화학회 웹사이트)
* {{웹 인용|url=http://www.ams.org/profession/prizes-awards/ams-prizes/fulkerson-prize|제목= Delbert Ray Fulkerson Prize|출판사=American Mathematical Society|언어=en}} (미국 수학회 웹사이트)

{{위키데이터 속성 추적}}

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