Русская Википедия:Премия Фалкерсона

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

Лауреаты премии

Год	Лауреаты	За что присуждена премия
1979	Ричард Карп	за классификацию многих важных NP-полных задач ^[1]
	Шаблон:Нп5 Вольфганг Хакен	за решение задачи четырёх красок ^[2]
	Пол Сеймур	за обобщение теоремы Форда — Фалкерсона на матроиды ^[3]
1982	Давид Юдин Аркадий Немировский Леонид Хачиян	за метод эллипсоидов в линейном программировании ^[4] ^[5]
	Шаблон:Нп5 Дмитрий Фаликман	за доказательство гипотезы ван дер Вардена о перманенте дважды стохастической матрицы ^[6]
	Шаблон:Нп5 Ласло Ловас Александр Схрейвер	за метод эллипсоидов в комбинаторной оптимизации ^[7]
1985	Шаблон:Нп5	за оценку границ расходимости целочисленных последовательностей ^[8]
	Хендрик Ленстра	за эффективный метод решения целочисленных программ с помощью геометрии чисел ^[9]
	Шаблон:Нп5	за полиномиальный алгоритм определения изоморфных графов ограниченной степени ^[10]
1988	Эва Тардош	за решение задачи о потоке минимальной стоимости алгоритмом сильно полиномиальной сложности ^[11]
1988	Нарендра Кармаркар	за алгоритм Кармаркара ^[12]
1991	Шаблон:Нп5 Шаблон:Нп5 Равиндран Каннан	за блуждающий алгоритм оценки объёма выпуклых тел ^[13]
	Альфред Леман	за аналоги бинарных матриц в теории совершенных графов ^[14]
	Шаблон:Нп5	за Шаблон:Нп5 о том, что любое полуалгебраическое множество эквивалентно пространству реализаций ориентированного матроида ^[15]
1994	Шаблон:Iw	за нахождение базисов пространства частично-полиномиальных функций ^[16]
	Шаблон:Нп5	за работу над гипотезой Хирша ^[17]
	Шаблон:Нп5	за шестицветное решение гипотезы Хадвигера ^[18]
1997	Шаблон:Нп5	за асимптотический анализ чисел Рамсея R(3,t) ^[19]
2000	Шаблон:Iw Шаблон:Iw	за алгоритмы аппроксимации в полуопределённом программировании ^[20]
2000	Шаблон:Iw Шаблон:Нп5 Шаблон:Нп5	за алгоритм распознавания сбалансированных бинарных матриц за полиномиальное время ^[21]
2003	Шаблон:Нп5 Берт Герардс Аджай Капур	за GF(4)-решение Шаблон:Нп5 для Шаблон:Нп5 ^[22]
	Бертран Гьюнин	за характеризацию запрещённых миноров слабо двудольных графов ^[23]
	Сатору Ивата Лиза Фляйшер Сатору Фудзисигэ Лекс Схрейвер	за доказательство сильной полиномиальности субмодулярной минимизации ^[24] ^[25]
2006	Шаблон:Нп5 Шаблон:Нп5 Шаблон:Нп5	за тест Агравала — Каяла — Саксены ^[26]
	Шаблон:Нп5 Шаблон:Нп5 Эрик Вигода	за аппроксимацию перманента ^[27]
	Шаблон:Нп5 Пол Сеймур	за теорему Робертсона — Сеймура ^[28]
2009	Шаблон:Нп5 Шаблон:Нп5 Пол Сеймур Робин Томас	за теорему о сильно идеальных графах ^[29]
	Дэниэл Спилмен Тэн Шанхуа	за Шаблон:Нп5 алгоритмов линейного программирования ^[30]^[31]
	Шаблон:Нп5 Шаблон:Iw	за доказательство гипотезы Кеплера для самой плотной упаковки шаров ^[32] ^[33]
2012	Санджив Арора Шаблон:Iw Умеш Вазирани	за снижение сложности алгоритма аппроксимации разделителей графов ^[34]
	Андерс Йохансон Шаблон:Нп5 Ву Ха Ван	за определение границы плотности дуг, с которой случайный граф может быть покрыт непересекающимися копиями данного меньшего графа ^[35]
	Ласло Ловас Шаблон:Iw	за оценку кратности подграфов в последовательностях плотных графов ^[36]
2015	Франсиско Сантос	за контрпример к гипотезе Хирша ^[37]
2018	Питер Аллен Юлия Бёттхер Саймон Гриффитс Шаблон:Iw Шаблон:Iw	за работу «Хроматические пороги графов» (Шаблон:Lang-en)
2018	Шаблон:Iw	за работу «Совпадающий политоп имеет экспоненциальную сложность расширенной формулировки» (Шаблон:Lang-en)
2021	Бела Чаба Шаблон:Нп5 Аллан Ло Шаблон:Нп5 Эндрю Треглоу	за доказательство гипотезы об 1-факторизации и гипотез о гамильтоновых разложениях ^[38]
	Шаблон:Нп5 Си Чэнь	за определение сложности вычисления статистических сумм ^[39]
	Шаблон:Нп5 Шаблон:Нп5	за разработку детерминированного алгоритма определения реберной связности ^[40]

Примечания

Шаблон:Примечания

Ссылки

↑ 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.
↑ Немировский А. С., Юдин Д. Б. Сложность задач и эффективность методов оптимизации, М.: Наука. Главная редакция физико-математической литературы, 1979. — 384 с.
↑ Л. Г. Хачиян, «Полиномиальные алгоритмы в линейном программировании», Ж. вычисл. матем. и матем. физ., 20:1 (1980), 51-68.
↑ Д. И. Фаликман, «Доказательство гипотезы Ван дер Вардена о перманенте дважды стохастической матрицы», Матем. заметки, 29:6 (1981), 931—938.
↑ Martin Grötschel, László Lovász and Alexander Schrijver, «The ellipsoid method and its consequences in combinatorial optimization», Combinatorica 1: 169—197, 1981.
↑ Jozsef Beck, «Roth’s estimate of the discrepancy of integer sequences is nearly sharp», Combinatorica 1 (4): 319—325, 1981.
↑ 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.
↑ Éva Tardos, "A strongly polynomial minimum cost circulation algorithm, " Combinatorica 5: 247—256, 1985.
↑ Narendra Karmarkar, "A new polynomial-time algorithm for linear programming, " Combinatorica 4:373-395, 1984.
↑ 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.
↑ Н. Е. Мнев, «Топология многообразий комбинаторных типов проективных конфигураций и выпуклых многогранников Шаблон:Wayback», кандидатская диссертация, 116 стр., Ленинград, 1986.
↑ 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 K₆-free graphs, " Combinatorica 13: 279—361, 1993.
↑ Jeong Han Kim, "The Ramsey Number R(3,t) Has Order of Magnitude t²/log t, " Random Structures and Algorithms 7 (3): 173—207, 1995.
↑ 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.
↑ Michele Conforti, Gérard Cornuéjols, M. R. Rao, «Decomposition of balanced matrices», Journal of Combinatorial Theory, Series B, 77 (2): 292—406, 1999.
↑ 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.
↑ 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.
↑ Manindra Agrawal, Neeraj Kayal and Nitin Saxena, «PRIMES is in P», Annals of Mathematics, 160 (2): 781—793, 2004.
↑ 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.
↑ Neil Robertson and Paul Seymour, "Graph Minors. XX. Wagner’s conjecture, " Journal of Combinatorial Theory, Series B, 92 (2): 325—357, 2004.
↑ 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.
↑ Шаблон:Cite web
↑ 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.
↑ 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, Balázs Szegedy, «Limits of dense graph sequences», Journal of Combinatorial Theory, Series B, 96: 933—957, 2006.
↑ Шаблон:Публикация Шаблон:MR.
↑ "Proof of the 1-factorization and Hamilton decomposition conjectures", Memoirs of the American Mathematical Society, vol. 244, no. 1154, 2016
↑ "Complexity of Counting CSP with Complex Weights", Journal of the ACM, vol. 64, no. 3, 2017
↑ "Deterministic Edge Connectivity in Near-Linear Time", Journal of the ACM, vol. 66, no. 1, 2018

[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] Л. Г. Хачиян, «Полиномиальные алгоритмы в линейном программировании», Ж. вычисл. матем. и матем. физ., 20:1 (1980), 51-68.

[6] Д. И. Фаликман, «Доказательство гипотезы Ван дер Вардена о перманенте дважды стохастической матрицы», Матем. заметки, 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] Н. Е. Мнев, «Топология многообразий комбинаторных типов проективных конфигураций и выпуклых многогранников Шаблон:Wayback», кандидатская диссертация, 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 K₆-free graphs, " Combinatorica 13: 279—361, 1993.

[19] Jeong Han Kim, "The Ramsey Number R(3,t) Has Order of Magnitude t²/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] Шаблон:Cite web

[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, Balázs Szegedy, «Limits of dense graph sequences», Journal of Combinatorial Theory, Series B, 96: 933—957, 2006.

[37] Шаблон:Публикация Шаблон:MR.

[38] "Proof of the 1-factorization and Hamilton decomposition conjectures", Memoirs of the American Mathematical Society, vol. 244, no. 1154, 2016

[39] "Complexity of Counting CSP with Complex Weights", Journal of the ACM, vol. 64, no. 3, 2017

[40] "Deterministic Edge Connectivity in Near-Linear Time", Journal of the ACM, vol. 66, no. 1, 2018

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]

[38]

[39]

[40]

Партнерские ресурсы
Криптовалюты	Обмен криптовалют - www.bestchange.ru Криптовалютная биржа CoinEx Криптовалютная биржа Binance HIVE OS - операционная система для майнинга e4pool - Мультивалютный пул для майнинга.
Магазины	AliExpress — глобальная виртуальная (в Интернете) торговая площадка, предоставляющая возможность покупать товары производителей из КНР; computeruniverse.net - Интернет-магазин компьютеров(Промо код 5 Евро на первую покупку:FWWC3ZKQ);
Хостинг	DigitalOcean - американский провайдер облачных инфраструктур, с главным офисом в Нью-Йорке и с центрами обработки данных по всему миру;
Разное	Викиум - Онлайн-тренажер для мозга Like Центр - Центр поддержки и развития предпринимательства. Gamersbay - лучший магазин по бустингу для World of Warcraft. Ноотропы OmniMind N°1 - Усиливает мозговую активность. Повышает мотивацию. Улучшает память. Санкт-Петербургская школа телевидения - это федеральная сеть образовательных центров, которая имеет филиалы в 37 городах России. Lingualeo.com — интерактивный онлайн-сервис для изучения и практики английского языка в увлекательной игровой форме. Junyschool (Джунискул) – международная школа программирования и дизайна для детей и подростков от 5 до 17 лет, где ученики осваивают компьютерную грамотность, развивают алгоритмическое и креативное мышление, изучают основы программирования и компьютерной графики, создают собственные проекты: игры, сайты, программы, приложения, анимации, 3D-модели, монтируют видео. Умназия - Интерактивные онлайн-курсы и тренажеры для развития мышления детей 6-13 лет SkillBox - это один из лидеров российского рынка онлайн-образования. Среди партнеров Skillbox ведущий разработчик сервисного дизайна AIC, медиа-компания Yoola, первое и самое крупное русскоязычное аналитическое агентство Tagline, онлайн-школа дизайна и иллюстрации Bang! Bang! Education, оператор PR-рынка PACO, студия рисования Draw&Go, агентство performance-маркетинга Ingate, scrum-студия Sibirix, имидж-лаборатория Персона. «Нетология» — это университет по подготовке и дополнительному обучению специалистов в области интернет-маркетинга, управления проектами и продуктами, дизайна, Data Science и разработки. В рамках Нетологии студенты получают ценные теоретические знания от лучших экспертов Рунета, выполняют практические задания на отработку полученных навыков, общаются с экспертами и единомышленниками. Познакомиться со всеми продуктами подробнее можно на сайте https://netology.ru, линейка курсов и профессий постоянно обновляется. StudyBay Brazil – это онлайн биржа для португалоговорящих студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт. Автор24 — самая большая в России площадка по написанию учебных работ: контрольные и курсовые работы, дипломы, рефераты, решение задач, отчеты по практике, а так же любой другой вид работы. Сервис сотрудничает с более 70 000 авторов. Более 1 000 000 работ уже выполнено. StudyBay – это онлайн биржа для англоязычных студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт.

Русская Википедия:Премия Фалкерсона

Лауреаты премии

Примечания

Ссылки

Навигация

Действия на странице

Действия на странице

Персональные инструменты

Навигация

Поиск

Инструменты