위키백과

풀커슨상

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

역사 편집

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

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

수상자 편집

연도 수상자 논문
1979 리처드 매닝 카프(영어: Richard Manning Karp) [1]
케네스 아펠, 볼프강 하켄(독일어: Wolfgang Haken) [2]
폴 시모어(영어: Paul Seymour) [3]
1982 다비트 보리소비치 유딘(러시아어: Давид Борисович Юдин), 아르카디 세묘노비치 네미롭스키(러시아어: Аркадий Семёнович Немиро́вский), 레오니트 겐리호비치 하치얀(러시아어: Леонид Генрихович Хачиян, 아르메니아어: Լեոնիդ Գենրիխովիչ Խաչիյան), 마르틴 그뢰첼(독일어: Martin Grötschel), 로바스 라슬로, 알렉산더르 스흐레이버르(네덜란드어: Alexander Schrijver) [4][5][6]
게오르기 페트로비치 예고리체프(러시아어: Георгий Петрович Его́рычев), 드미트리 이힐로비치 팔리크만(러시아어: Дмитрий Ихилович Фаликман) [7][8]
1985 베크 요제프(헝가리어: Beck József) [9]
헨드릭 빌럼 렌스트라 2세(네덜란드어: Hendrik Willem Lenstra, Jr) [10]
유진 마이클 럭스(영어: Eugene Michael Luks) [11]
1988 터르도시 에버(헝가리어: Tardos Éva) [12]
나렌드라 크리슈나 카르마르카르(Narendra Krishna Karmarkar) [13]
1991 마틴 다이어(영어: Martin E. Dyer), 앨런 프리즈(영어: Alan M. Frieze), 라빈드란 칸난(Ravindran Kannan) [14]
앨프리드 리먼(영어: Alfred Lehman) [15]
니콜라이 예브게니예비치 므뇨프(러시아어: Николай Евгеньевич Мнёв) [16]
1994 루이스 빌레라(영어: Louis J. Billera) [17]
길 칼라이(히브리어: גיל קלעי) [18]
닐 로버트슨(영어: Neil Robertson), 폴 시모어(영어: Paul Seymour), 로빈 토머스(영어: Robin Thomas) [19]
1997 김정한 [20]
2000 미셸 그자비에 괴망(프랑스어: Michel Xavier Goemans), 데이비드 윌리엄슨(영어: David P. Williamson) [21]
미켈란젤로 콘포르티(이탈리아어: Michelangelo Conforti), 제라르 피에르 코르뉘에졸(프랑스어: Gérard Pierre Cornuéjols), 멘두 람모한 라오(Mendu Rammohan Rao) [22]
2003 제임스 길런(영어: James F. Geelen), 알버르트 헤라르츠(네덜란드어: Albert M. H. Gerards), 아자이 카푸르(Ajai Kapoor) [23]
버트런드 게닌(영어: Bertrand Guenin) [24]
이와타 사토루(일본어: 岩田 覚), Lisa Fleischer, 후지시게 사토루(일본어: 藤重 悟), 알렉산더르 스흐레이버르(네덜란드어: Alexander Schrijver) [25][26]
2006 마닌드라 아가르왈(Manindra Agarwal), 니라지 카얄(Neeraj Kayal), 니틴 삭세나(Nitin Saxena) [27]
마크 제럼(영어: Mark Jerrum), 앨리스터 싱클레어(영어: Alistair Sinclair), 에릭 비고다(영어: Eric Vigoda) [28]
닐 로버트슨(영어: Neil Robertson), 폴 시모어(영어: Paul Seymour) [29]
2009 마리아 추드노브스키(영어: Maria Chudnovsky, 히브리어: מריה צ'ודנובסקי), 닐 로버트슨(영어: Neil Robertson), 폴 시모어(영어: Paul Seymour), 로빈 토머스(영어: Robin Thomas) [30]
대니얼 앨런 스필먼(영어: Daniel Alan Spielman), 텅샹화(중국어 간체자: 滕尚华, 정체자: 滕尚華, 병음: Téng Shànghuá) [31]
토머스 캘리스터 헤일스(영어: Thomas Callister Hales), 새뮤얼 퍼구슨(영어: Samuel P. Ferguson) [32][33]
2012 산지브 아로라(Sanjeev Arora), 사티시 라오(Satish Rao), 우메시 바지라니(Umesh Vazirani) [34]
안데르스 요한손(스웨덴어: Anders Johansson), 제프 칸(영어: Jeff Kahn), 부하반(베트남어: Vũ Hà Văn) [35]
로바스 라슬로, 세게디 벌라주(헝가리어: Szegedy Balázs) [36]

참고 문헌 편집

  1. ↑ Richard M. Karp, "On the computational complexity of combinatorial problems", Networks 5: 45–68, 1975.
  2. ↑ Kenneth Appel and Wolfgang Haken, "Every planar map is four colorable, Part I: Discharging," Illinois Journal of Mathematics 21: 429–490, 1977
  3. ↑ Paul Seymour, "The matroids with the max-flow min-cut property," Journal of Combinatorial Theory, Series B, 23: 189–222, 1977.
  4. ↑ 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.
  5. ↑ Leonid Khachiyan, "A polynomial algorithm in linear programming," Akademiia Nauk SSSR. Doklady 244: 1093–1096, 1979.
  6. ↑ Martin Grötschel, László Lovász and Alexander Schrijver, "The ellipsoid method and its consequences in combinatorial optimization," Combinatorica 1: 169–197, 1981.
  7. ↑ G. P. Egorychev, "The solution of van der Waerden's problem for permanents," Akademiia Nauk SSSR. Doklady 258: 1041–1044, 1981.
  8. ↑ 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.
  9. ↑ Jozsef Beck, "Roth's estimate of the discrepancy of integer sequences is nearly sharp," Combinatorica 1 (4): 319–325, 1981.
  10. ↑ H. W. Lenstra, Jr., "Integer programming with a fixed number of variables," Mathematics of Operations Research 8 (4): 538–548, 1983.
  11. ↑ 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.
  12. ↑ Éva Tardos, "A strongly polynomial minimum cost circulation algorithm," Combinatorica 5: 247-256, 1985.
  13. ↑ Narendra Karmarkar, "A new polynomial-time algorithm for linear programming," Combinatorica 4:373–395, 1984.
  14. ↑ 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.
  15. ↑ 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.
  16. ↑ 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.
  17. ↑ Louis Billera, "Homology of smooth splines: Generic triangulations and a conjecture of Strang", Transactions of the AMS 310: 325–340, 1988.
  18. ↑ Gil Kalai, "Upper bounds for the diameter and height of graphs of the convex polyhedra", Discrete and Computational Geometry 8: 363–372, 1992.
  19. ↑ Neil Robertson, Paul Seymour and Robin Thomas, "Hadwiger's conjecture for  -free graphs," Combinatorica 13: 279–361, 1993.
  20. ↑ 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.
  21. ↑ 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.
  22. ↑ 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.
  23. ↑ 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.
  24. ↑ Bertrand Guenin, "A characterization of weakly bipartite graphs," Journal of Combinatorial Theory, Series B, 83 (1): 112–168, 2001.
  25. ↑ Satoru Iwata, Lisa Fleischer, Satoru Fujishige, "A combinatorial strongly polynomial algorithm for minimizing submodular functions," Journal of the ACM, 48 (4): 761–777, 2001.
  26. ↑ Alexander Schrijver, "A combinatorial algorithm minimizing submodular functions in strongly polynomial time," Journal of Combinatorial Theory, Series B 80 (2): 346–355, 2000.
  27. ↑ Manindra Agrawal, Neeraj Kayal and Nitin Saxena, "PRIMES is in P," Annals of Mathematics, 160 (2): 781–793, 2004.
  28. ↑ 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.
  29. ↑ Neil Robertson and Paul Seymour, "Graph Minors. XX. Wagner's conjecture," Journal of Combinatorial Theory, Series B, 92 (2): 325–357, 2004.
  30. ↑ Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas, "The strong perfect graph theorem", Annals of Mathematics, 164: 51–229, 2006.
  31. ↑ 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.
  32. ↑ Thomas C. Hales, "A proof of the Kepler conjecture", Annals of Mathematics 162: 1063–1183, 2005.
  33. ↑ Samuel P. Ferguson, "Sphere Packings, V. Pentahedral Prisms", Discrete and Computational Geometry 36: 167–204, 2006.
  34. ↑ Sanjeev Arora, Satish Rao, and Umesh Vazirani, "Expander flows, geometric embeddings and graph partitioning", Journal of the ACM 56: 1-37, 2009.
  35. ↑ Anders Johansson, Jeff Kahn, and Van H. Vu, "Factors in random graphs", Random Structures and Algorithms 33: 1-28, 2008.
  36. ↑ László Lovász and Balázs Szegedy, "Limits of dense graph sequences", Journal of Combinatorial Theory, Series B, 96: 933-957, 2006.

외부 링크 편집

원본 주소 "https://ko.wikipedia.org/w/index.php?title=풀커슨상&oldid=31472678"