Премия Фалкерсона

Поделись знанием:
Перейти к: навигация, поиск

Премия Фалкерсона (англ.) вручается за выдающиеся научные статьи в области дискретной математики и спонсируется совместно Обществом математической оптимизации (англ.) (MOS) и Американским математическим обществом (AMS). Каждые три года проходит международный симпозиум MOS, на котором объявляются получателей премии (не более трёх пунктов, каждый из которых может включать нескольких учёных). Премия включает денежную награду в полторы тысячи долларов, изначально шедшую из фонда, организованного друзьями Делберта Рея Фалкерсона после его смерти для стимуляции математических работ в его области.



Получатели премии

Источники

  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. Немировский А. С., Юдин Д. Б. Сложность задач и эффективность методов оптимизации, М.: Наука. Главная редакция физико-математической литературы, 1979. — 384 с.
  5. Л. Г. Хачиян, «[mi.mathnet.ru/zvmmf5239 Полиномиальные алгоритмы в линейном программировании]», Ж. вычисл. матем. и матем. физ., 20:1 (1980), 51-68.
  6. Д. И. Фаликман, «[mi.mathnet.ru/mz6253 Доказательство гипотезы Ван дер Вардена о перманенте дважды стохастической матрицы]», Матем. заметки, 29:6 (1981), 931—938.
  7. Martin Grötschel, László Lovász and Alexander Schrijver, «The ellipsoid method and its consequences in combinatorial optimization», Combinatorica 1: 169—197, 1981.
  8. Jozsef Beck, «Roth’s estimate of the discrepancy of integer sequences is nearly sharp», Combinatorica 1 (4): 319—325, 1981.
  9. H. W. Lenstra, Jr., "Integer programming with a fixed number of variables, " Mathematics of Operations Research 8 (4): 538—548, 1983.
  10. 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.
  11. Éva Tardos, "A strongly polynomial minimum cost circulation algorithm, " Combinatorica 5: 247—256, 1985.
  12. Narendra Karmarkar, "A new polynomial-time algorithm for linear programming, " Combinatorica 4:373-395, 1984.
  13. 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.
  14. 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.
  15. Н. Е. Мнев, «[www.pdmi.ras.ru/~mnev/mnev_phd1.pdf Топология многообразий комбинаторных типов проективных конфигураций и выпуклых многогранников]», кандидатская диссертация, 116 стр., Ленинград, 1986.
  16. Louis Billera, «Homology of smooth splines: Generic triangulations and a conjecture of Strang», Transactions of the AMS 310: 325—340, 1988.
  17. Gil Kalai, «Upper bounds for the diameter and height of graphs of the convex polyhedra», Discrete and Computational Geometry 8: 363—372, 1992.
  18. Neil Robertson, Paul Seymour and Robin Thomas, "Hadwiger’s conjecture for K6-free graphs, " Combinatorica 13: 279—361, 1993.
  19. Jeong Han Kim, "The Ramsey Number R(3,t) Has Order of Magnitude t2/log t, " Random Structures and Algorithms 7 (3): 173—207, 1995.
  20. 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.
  21. Michele Conforti, Gérard Cornuéjols, M. R. Rao, «Decomposition of balanced matrices», Journal of Combinatorial Theory, Series B, 77 (2): 292—406, 1999.
  22. 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.
  23. Bertrand Guenin, «A characterization of weakly bipartite graphs», Journal of Combinatorial Theory, Series B, 83 (1): 112—168, 2001.
  24. Satoru Iwata, Lisa Fleischer, Satoru Fujishige, «A combinatorial strongly polynomial algorithm for minimizing submodular functions», Journal of the ACM, 48 (4): 761—777, 2001.
  25. Alexander Schrijver, «A combinatorial algorithm minimizing submodular functions in strongly polynomial time», Journal of Combinatorial Theory, Series B 80 (2): 346—355, 2000.
  26. Manindra Agrawal, Neeraj Kayal and Nitin Saxena, «PRIMES is in P», Annals of Mathematics, 160 (2): 781—793, 2004.
  27. Mark Jerrum, Alistair Sinclair, 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.
  28. Neil Robertson and Paul Seymour, "Graph Minors. XX. Wagner’s conjecture, " Journal of Combinatorial Theory, Series B, 92 (2): 325—357, 2004.
  29. Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas, «The strong perfect graph theorem», Annals of Mathematics, 164: 51-229, 2006.
  30. 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.
  31. Thomas C. Hales, «A proof of the Kepler conjecture», Annals of Mathematics 162: 1063—1183, 2005.
  32. Samuel P. Ferguson, «Sphere Packings, V. Pentahedral Prisms», Discrete and Computational Geometry 36: 167—204, 2006.
  33. Sanjeev Arora, Satish Rao, and Umesh Vazirani, «Expander flows, geometric embeddings and graph partitioning», Journal of the ACM 56: 1-37, 2009.
  34. Anders Johansson, Jeff Kahn, and Van H. Vu, «Factors in random graphs», Random Structures and Algorithms 33: 1-28, 2008.
  35. László Lovász, Balázs Szegedy, «Limits of dense graph sequences», Journal of Combinatorial Theory, Series B, 96: 933—957, 2006.
  36. Francisco Santos. A counterexample to the Hirsch Conjecture // Annals of Mathematics. — 2012. — Vol. 176. — P. 383-412. — arXiv:1006.2814. — DOI:10.4007/annals.2012.176.1.7. MR[www.ams.org/mathscinet-getitem?mr=2925387 2925387].</span>
  37. </ol>

Напишите отзыв о статье "Премия Фалкерсона"

Ссылки

  • [www.ams.org/prizes/fulkerson-prize.html Официальный сайт премии]
  • [www.ams.org/profession/prizes-awards/pabrowse Список получавших премию]

Отрывок, характеризующий Премия Фалкерсона

А Мавра Кузминишна еще долго с мокрыми глазами стояла перед затворенной калиткой, задумчиво покачивая головой и чувствуя неожиданный прилив материнской нежности и жалости к неизвестному ей офицерику.


В недостроенном доме на Варварке, внизу которого был питейный дом, слышались пьяные крики и песни. На лавках у столов в небольшой грязной комнате сидело человек десять фабричных. Все они, пьяные, потные, с мутными глазами, напруживаясь и широко разевая рты, пели какую то песню. Они пели врозь, с трудом, с усилием, очевидно, не для того, что им хотелось петь, но для того только, чтобы доказать, что они пьяны и гуляют. Один из них, высокий белокурый малый в чистой синей чуйке, стоял над ними. Лицо его с тонким прямым носом было бы красиво, ежели бы не тонкие, поджатые, беспрестанно двигающиеся губы и мутные и нахмуренные, неподвижные глаза. Он стоял над теми, которые пели, и, видимо воображая себе что то, торжественно и угловато размахивал над их головами засученной по локоть белой рукой, грязные пальцы которой он неестественно старался растопыривать. Рукав его чуйки беспрестанно спускался, и малый старательно левой рукой опять засучивал его, как будто что то было особенно важное в том, чтобы эта белая жилистая махавшая рука была непременно голая. В середине песни в сенях и на крыльце послышались крики драки и удары. Высокий малый махнул рукой.
– Шабаш! – крикнул он повелительно. – Драка, ребята! – И он, не переставая засучивать рукав, вышел на крыльцо.
Фабричные пошли за ним. Фабричные, пившие в кабаке в это утро под предводительством высокого малого, принесли целовальнику кожи с фабрики, и за это им было дано вино. Кузнецы из соседних кузень, услыхав гульбу в кабаке и полагая, что кабак разбит, силой хотели ворваться в него. На крыльце завязалась драка.
Целовальник в дверях дрался с кузнецом, и в то время как выходили фабричные, кузнец оторвался от целовальника и упал лицом на мостовую.
Другой кузнец рвался в дверь, грудью наваливаясь на целовальника.
Малый с засученным рукавом на ходу еще ударил в лицо рвавшегося в дверь кузнеца и дико закричал:
– Ребята! наших бьют!
В это время первый кузнец поднялся с земли и, расцарапывая кровь на разбитом лице, закричал плачущим голосом:
– Караул! Убили!.. Человека убили! Братцы!..
– Ой, батюшки, убили до смерти, убили человека! – завизжала баба, вышедшая из соседних ворот. Толпа народа собралась около окровавленного кузнеца.
– Мало ты народ то грабил, рубахи снимал, – сказал чей то голос, обращаясь к целовальнику, – что ж ты человека убил? Разбойник!
Высокий малый, стоя на крыльце, мутными глазами водил то на целовальника, то на кузнецов, как бы соображая, с кем теперь следует драться.
– Душегуб! – вдруг крикнул он на целовальника. – Вяжи его, ребята!
– Как же, связал одного такого то! – крикнул целовальник, отмахнувшись от набросившихся на него людей, и, сорвав с себя шапку, он бросил ее на землю. Как будто действие это имело какое то таинственно угрожающее значение, фабричные, обступившие целовальника, остановились в нерешительности.
– Порядок то я, брат, знаю очень прекрасно. Я до частного дойду. Ты думаешь, не дойду? Разбойничать то нонче никому не велят! – прокричал целовальник, поднимая шапку.
– И пойдем, ишь ты! И пойдем… ишь ты! – повторяли друг за другом целовальник и высокий малый, и оба вместе двинулись вперед по улице. Окровавленный кузнец шел рядом с ними. Фабричные и посторонний народ с говором и криком шли за ними.
У угла Маросейки, против большого с запертыми ставнями дома, на котором была вывеска сапожного мастера, стояли с унылыми лицами человек двадцать сапожников, худых, истомленных людей в халатах и оборванных чуйках.
– Он народ разочти как следует! – говорил худой мастеровой с жидкой бородйой и нахмуренными бровями. – А что ж, он нашу кровь сосал – да и квит. Он нас водил, водил – всю неделю. А теперь довел до последнего конца, а сам уехал.
Увидав народ и окровавленного человека, говоривший мастеровой замолчал, и все сапожники с поспешным любопытством присоединились к двигавшейся толпе.
– Куда идет народ то?
– Известно куда, к начальству идет.
– Что ж, али взаправду наша не взяла сила?
– А ты думал как! Гляди ко, что народ говорит.
Слышались вопросы и ответы. Целовальник, воспользовавшись увеличением толпы, отстал от народа и вернулся к своему кабаку.
Высокий малый, не замечая исчезновения своего врага целовальника, размахивая оголенной рукой, не переставал говорить, обращая тем на себя общее внимание. На него то преимущественно жался народ, предполагая от него получить разрешение занимавших всех вопросов.
– Он покажи порядок, закон покажи, на то начальство поставлено! Так ли я говорю, православные? – говорил высокий малый, чуть заметно улыбаясь.
– Он думает, и начальства нет? Разве без начальства можно? А то грабить то мало ли их.
– Что пустое говорить! – отзывалось в толпе. – Как же, так и бросят Москву то! Тебе на смех сказали, а ты и поверил. Мало ли войсков наших идет. Так его и пустили! На то начальство. Вон послушай, что народ то бает, – говорили, указывая на высокого малого.
У стены Китай города другая небольшая кучка людей окружала человека в фризовой шинели, держащего в руках бумагу.
– Указ, указ читают! Указ читают! – послышалось в толпе, и народ хлынул к чтецу.
Человек в фризовой шинели читал афишку от 31 го августа. Когда толпа окружила его, он как бы смутился, но на требование высокого малого, протеснившегося до него, он с легким дрожанием в голосе начал читать афишку сначала.
«Я завтра рано еду к светлейшему князю, – читал он (светлеющему! – торжественно, улыбаясь ртом и хмуря брови, повторил высокий малый), – чтобы с ним переговорить, действовать и помогать войскам истреблять злодеев; станем и мы из них дух… – продолжал чтец и остановился („Видал?“ – победоносно прокричал малый. – Он тебе всю дистанцию развяжет…»)… – искоренять и этих гостей к черту отправлять; я приеду назад к обеду, и примемся за дело, сделаем, доделаем и злодеев отделаем».
Последние слова были прочтены чтецом в совершенном молчании. Высокий малый грустно опустил голову. Очевидно было, что никто не понял этих последних слов. В особенности слова: «я приеду завтра к обеду», видимо, даже огорчили и чтеца и слушателей. Понимание народа было настроено на высокий лад, а это было слишком просто и ненужно понятно; это было то самое, что каждый из них мог бы сказать и что поэтому не мог говорить указ, исходящий от высшей власти.
Все стояли в унылом молчании. Высокий малый водил губами и пошатывался.
– У него спросить бы!.. Это сам и есть?.. Как же, успросил!.. А то что ж… Он укажет… – вдруг послышалось в задних рядах толпы, и общее внимание обратилось на выезжавшие на площадь дрожки полицеймейстера, сопутствуемого двумя конными драгунами.
Полицеймейстер, ездивший в это утро по приказанию графа сжигать барки и, по случаю этого поручения, выручивший большую сумму денег, находившуюся у него в эту минуту в кармане, увидав двинувшуюся к нему толпу людей, приказал кучеру остановиться.
– Что за народ? – крикнул он на людей, разрозненно и робко приближавшихся к дрожкам. – Что за народ? Я вас спрашиваю? – повторил полицеймейстер, не получавший ответа.
– Они, ваше благородие, – сказал приказный во фризовой шинели, – они, ваше высокородие, по объявлению сиятельнейшего графа, не щадя живота, желали послужить, а не то чтобы бунт какой, как сказано от сиятельнейшего графа…
– Граф не уехал, он здесь, и об вас распоряжение будет, – сказал полицеймейстер. – Пошел! – сказал он кучеру. Толпа остановилась, скучиваясь около тех, которые слышали то, что сказало начальство, и глядя на отъезжающие дрожки.
Полицеймейстер в это время испуганно оглянулся, что то сказал кучеру, и лошади его поехали быстрее.
– Обман, ребята! Веди к самому! – крикнул голос высокого малого. – Не пущай, ребята! Пущай отчет подаст! Держи! – закричали голоса, и народ бегом бросился за дрожками.
Толпа за полицеймейстером с шумным говором направилась на Лубянку.
– Что ж, господа да купцы повыехали, а мы за то и пропадаем? Что ж, мы собаки, что ль! – слышалось чаще в толпе.


Вечером 1 го сентября, после своего свидания с Кутузовым, граф Растопчин, огорченный и оскорбленный тем, что его не пригласили на военный совет, что Кутузов не обращал никакого внимания на его предложение принять участие в защите столицы, и удивленный новым открывшимся ему в лагере взглядом, при котором вопрос о спокойствии столицы и о патриотическом ее настроении оказывался не только второстепенным, но совершенно ненужным и ничтожным, – огорченный, оскорбленный и удивленный всем этим, граф Растопчин вернулся в Москву. Поужинав, граф, не раздеваясь, прилег на канапе и в первом часу был разбужен курьером, который привез ему письмо от Кутузова. В письме говорилось, что так как войска отступают на Рязанскую дорогу за Москву, то не угодно ли графу выслать полицейских чиновников, для проведения войск через город. Известие это не было новостью для Растопчина. Не только со вчерашнего свиданья с Кутузовым на Поклонной горе, но и с самого Бородинского сражения, когда все приезжавшие в Москву генералы в один голос говорили, что нельзя дать еще сражения, и когда с разрешения графа каждую ночь уже вывозили казенное имущество и жители до половины повыехали, – граф Растопчин знал, что Москва будет оставлена; но тем не менее известие это, сообщенное в форме простой записки с приказанием от Кутузова и полученное ночью, во время первого сна, удивило и раздражило графа.
Впоследствии, объясняя свою деятельность за это время, граф Растопчин в своих записках несколько раз писал, что у него тогда было две важные цели: De maintenir la tranquillite a Moscou et d'en faire partir les habitants. [Сохранить спокойствие в Москве и выпроводить из нее жителей.] Если допустить эту двоякую цель, всякое действие Растопчина оказывается безукоризненным. Для чего не вывезена московская святыня, оружие, патроны, порох, запасы хлеба, для чего тысячи жителей обмануты тем, что Москву не сдадут, и разорены? – Для того, чтобы соблюсти спокойствие в столице, отвечает объяснение графа Растопчина. Для чего вывозились кипы ненужных бумаг из присутственных мест и шар Леппиха и другие предметы? – Для того, чтобы оставить город пустым, отвечает объяснение графа Растопчина. Стоит только допустить, что что нибудь угрожало народному спокойствию, и всякое действие становится оправданным.