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

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

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

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

Примечания

  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. ↑ Н. Е. Мнев, «Топология многообразий комбинаторных типов проективных конфигураций и выпуклых многогранников Архивная копия от 11 марта 2014 на Wayback Machine», кандидатская диссертация, 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. ↑ Mathematical Optimization Society 2009 Fulkerson Prize Citation. Дата обращения: 1 июля 2019. Архивировано 4 декабря 2021 года.
  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. ↑ 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: 2925387.
  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
  41. ↑ 2024 Delbert Ray Fulkerson Prize Awarded. News from the AMS. American Mathematical Society (23 июля 2024). Дата обращения: 25 июля 2024.

Ссылки

Read other articles:

Ashabulkahfi

Lukisan yang menggambarkan Ashabulkahfi dan seekor anjing (pojok kiri bawah) yang menjaganya selama mereka tertidur di dalam gua atas kehendak Allah Ilustrasi dari Menologium Kaisar Basilius II Ashabulkahfi atau Tujuh yang Tertidur (Bahasa Arab: اصحاب الکهف, aṣḥāb al-kahf, Bahasa Yunani: επτά κοιμώμενοι, hepta koimōmenoi, Bahasa Latin: Septem dormientes, Bahasa Inggris: The Seven Sleepers) adalah kisah agama Kristen dan Islam yang menceritakan tujuh pemuda yang t...

 

 

Tokyo Rose

World War II Japanese propagandists For other uses, see Tokyo Rose (disambiguation). JOAK microphone and Iva Toguri D'Aquino (dubbed Tokyo Rose by some), National Museum of American History Tokyo Rose (alternative spelling Tokio Rose) was a name given by Allied troops in the South Pacific during World War II to all female English-speaking radio broadcasters of Japanese propaganda.[1] The programs were broadcast in the South Pacific and North America to demoralize Allied forces abroad ...

 

 

Hohenau

Hohenau Lambang kebesaranLetak Hohenau NegaraJermanNegara bagianBayernWilayahNiederbayernKreisFreyung-GrafenauSubdivisions20 ortsteilPemerintahan • MayorEduard Schmid (CSU)Luas • Total43,12 km2 (1,665 sq mi)Ketinggian804 m (2,638 ft)Populasi (2013-12-31)[1] • Total3.326 • Kepadatan0,77/km2 (2,0/sq mi)Zona waktuWET/WMPET (UTC+1/+2)Kode pos94545Kode area telepon08558Pelat kendaraanFRGSitus webwww.hohenau....

Candice Bergen

Candice BergenCandice Bergen, 1993LahirCandice Patricia Bergen9 Mei 1946 (umur 77)Beverly Hills, California, U.S.PekerjaanActress, fashion modelTahun aktif1965–presentSuami/istriLouis Malle (1980–95)Marshall Rose (2000—) Candice Patricia Bergen (lahir 9 Mei 1946) merupakan seorang aktris berkebangsaan Amerika Serikat yang memenangkan nominasi Golden Globe Award dan Emmy Award. Dia dilahirkan di Beverly Hills, California. Dia berkarier di dunia film sejak tahun 1966. Filmograf...

 

 

Anne Marie d'Orléans

Queen of Sardinia and Duchess of Savoy For La Grande Mademoiselle, the greatest heiress in Europe, see Anne Marie Louise d'Orléans. Anne Marie d'OrléansAnne Marie d’Orleans by Louis Ferdinand Elle the Younger, 1683Queen consort of SardiniaTenure24 August 1720 – 26 August 1728Queen consort of SicilyTenure11 April 1713 – 17 February 1720Coronation24 December 1713Duchess consort of SavoyTenure10 April 1684 – 26 August 1728Born(1669-08-27)27 August 1669Château de Saint-Cloud, Franc...

 

 

Last Night (2010 film)

Last NightSutradaraMassy TadjedinProduserBuddy Enright (Executive)Christophe RiandeeMassy TadjedinNick WechslerDitulis olehMassy TadjedinPemeranKeira KnightleySam WorthingtonEva MendesGuillaume CanetStephanie RomanovPenata musikClint MansellSinematograferPeter DemingPenyuntingSusan E. MorseDistributorGaumontMiramax Films (USA)Tanggal rilis 18 September 2010 (2010-09-18) (TIFF) 16 Februari 2011 (2011-02-16) (France) 6 Mei 2011 (2011-05-06) (United States) Duras...

Italcementi

Italcementi Création 1864 Dates clés 1992 : rachat de Ciments Français 2015 : rachat par HeidelbergCement Group Forme juridique S.p.A. - S.A. Slogan A world class local business Siège social Peschiera Borromeo, Italie Direction Roberto Callieri[1] Actionnaires Heidelberg Materials Activité Matériaux de construction Produits Ciment et dérivés Société mère Heidelberg Materials Filiales Italcementi (Canada) (d) Effectif 21 000 (2009) Site web www.italcementigroup.com C...

 

 

Daftar Duta Besar Indonesia untuk Brasil

Duta Besar Indonesia untuk BrasilLambang Kementerian Luar Negeri Republik IndonesiaPetahanaEdy Yusupsejak 7 Januari 2019KantorBrasília, BrasilDitunjuk olehPresiden IndonesiaPejabat perdanaRaden SudjonoDibentuk1953Situs webkemlu.go.id/brasilia/id Berikut adalah daftar diplomat Indonesia yang pernah menjabat Duta Besar Republik Indonesia untuk Brasil: No. Foto Nama Mulai menjabat Selesai menjabat Merangkap Diangkat oleh Ref. 1 Raden Sudjono 5 Maret 1953 1958   Soekarno [1] 2 ...

 

 

Grab (ship)

Bombay grab – a cruiser of the Bombay Marine, unknown artist c. 1780, British Library A grab was a type of ship common on the Malabar Coast in the 18th and 19th centuries. The name derives from ghurāb or ghorāb, Arabic for raven, which in turn came into Marathi and Konkani as gurab. The ghurāb was originally a galley, but the type evolved.[1] The grab combined an indigenous hull form with a pointed prow, with or without a bowsprit, combined with European rigging on two to three m...

Division 1 1996-1997

Division 1 1996-1997 Competizione Division 1 Sport Calcio Edizione 59ª Organizzatore LFP Date dal 9 agosto 1996al 24 maggio 1997 Luogo  Francia Partecipanti 20 Formula Girone unico Sito web lfp.fr Risultati Vincitore Monaco(6º titolo) Retrocessioni CaenNancyLillaNizza Statistiche Miglior giocatore Sonny Anderson Miglior marcatore Stéphane Guivarc'h (22) Incontri disputati 380 Gol segnati 884 (2,33 per incontro) Pubblico 10 378 398 (27 312 per inc...

 

 

Peter Parker (Marvel Cinematic Universe)

Character in the Marvel Cinematic Universe Spider-Man (Marvel Cinematic Universe) redirects here. For the films, see Spider-Man (2017 film series). Fictional character Peter ParkerMarvel Cinematic Universe characterTom Holland as Peter Parker / Spider-Man in Spider-Man: Far From Home (2019)First appearanceCaptain America: Civil War (2016)Based onSpider-Manby Stan LeeSteve DitkoAdapted byChristopher MarkusStephen McFeelyPortrayed byTom HollandVoiced byHudson Thames (Disney+ animated series)In-...

 

 

Rivalta di Torino

Cet article est une ébauche concernant une localité italienne et le Piémont. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants. Rivalta di Torino Nom piémontais Rivàuta Administration Pays Italie Région Piémont  Ville métropolitaine Turin  Code postal 10040 Code ISTAT 001214 Code cadastral H335 Préfixe tel. 011 Démographie Gentilé rivaltesi Population 20 061 hab. (31-08-2021[1]) Densi...

爱德华·谢瓦尔德纳泽

爱德华·谢瓦尔德纳泽ედუარდ შევარდნაძე第2任格鲁吉亚總統任期1995年11月26日—2003年11月23日前任茲維亞德·加姆薩胡爾季阿继任米哈伊尔·萨卡什维利苏联外交部部长任期1985年7月2日—1990年12月20日总书记米哈伊尔·戈尔巴乔夫前任安德烈·葛罗米柯继任亚历山大·别斯梅尔特内赫 个人资料出生(1928-01-25)1928年1月25日苏联外高加索苏维埃联邦社会主义共和国古...

 

 

الألعاب الأولمبية الصيفية 2024

هذه المقالة حول حدث رياضي مستقبليّ أو منتظر. ومن الممكن أن تكون المعلومات حوله متضاربةً وقد يكون مضمونها متغيرًا تغيراً كبيراً خاصة مع اقتراب انطلاق الحدث. لا تتردد في تحسين المعلومات عن طريق الاستشهاد بمصادر موثوقة. كل عنصر ذو أخبار غير موسوعية يوجه إلى ويكي الأخبار. الأل�...

 

 

Alf and Alfhild

Legends in Norse mythology On Viking Expeditions of Highborn Maids: Two female warriors, of royal family according to the crowns on their heads, are participating in a sea battle. From Olaus Magnus' A Description of the Northern Peoples from 1555. On Alf, the Defender of Chastity: Alf, a suitor to the princess Alvilda kills two serpents who are guarding her chastity. To vex them he wears a bloody hide over his armour. From Olaus Magnus' A Description of the Northern Peoples, 1555. According t...

Driving in the United Kingdom

This article relies largely or entirely on a single source. Relevant discussion may be found on the talk page. Please help improve this article by introducing citations to additional sources.Find sources: Driving in the United Kingdom – news · newspapers · books · scholar · JSTOR (November 2007) Overview of driving in the United Kingdom Driving in the United Kingdom is governed by various legal powers and in some cases is subject to the passing of a d...

 

 

Renault Safrane

Renault Safrane Общие данные Производитель Renault Годы производства 1992—1998 2008—2012 (Мексика,переименованный Renault Latitude) Сборка Usine Renault de Sandouville (Сандувиль, Франция) Класс бизнес-класс Дизайн и конструкция Тип кузова 5‑дв. лифтбек (5‑мест.) Компоновка переднемоторная, переднеприво...

 

 

Czech Republic men's national under-19 volleyball team

Czech Republic Boys' U19AssociationCzech Volleyball AssociationConfederationCEVUniforms Home Away Third Youth Olympic GamesAppearancesNo AppearancesFIVB U19 World ChampionshipAppearances6 (First in 1997)Best result4th place : (2003)Europe U19 / U18 ChampionshipAppearances7 (First in 1997)Best result Champions : (2017)www.cvf.cz (in Czech) The Czech Republic men's national under-19 volleyball team represents Czech Republic in international men's volleyball competitions and friendly m...

Neighbours

Australian soap opera (1985–present) This article is about the soap opera. For other articles with similar titles, see Neighbor. NeighboursGenreSoap operaCreated byReg WatsonStarringCastTheme music composer Tony Hatch (theme music) Jackie Trent (lyrics) Opening themeNeighbours themeCountry of origin Australia Original languageEnglishNo. of seasons40No. of episodes9,083ProductionExecutive producerJason HerbisonProducerAndrew ThompsonProduction locationsMelbourne, AustraliaRunning time22–24...

 

 

Crazy World Tour Live... Berlin 1991

1991 video by ScorpionsCrazy World Tour Live... Berlin 1991Video by ScorpionsReleased1991RecordedDeutschlandhalle, Berlin, Germany, December 1990GenreHard rock, heavy metalLength75 min. LabelMercury/PolyGramProducerDana Marshall, Scott McGheeScorpions video albums chronology To Russia with Love and Other Savage Amusements(1988) Crazy World Tour Live... Berlin 1991(1991) Moment of Glory Live(2000) Crazy World Tour Live... Berlin 1991 is a 1991 live video by German band Scorpions. The c...