Новости программирования

Премия AMS за алгоритм Max Cut

[ad_1]

Мишель Гоэманс и Дэвид Уильямсон недавно получили премию AMS Steele Prize 2022 года за выдающийся вклад в исследования за статью 1995 года, в которой основное внимание уделялось проблеме Max-Cut, основной проблеме комбинаторной оптимизации, и которая оказала устойчивое влияние на области теоретической информатики и теория оптимизации.

amsbanner

Премия Стила находится в ведении Американского математического общества (AMS). Первоначально он был основан в 1970 году в честь Джорджа Дэвида Биркхоффа, Уильяма Фогга Осгуда и Уильяма Каспара Граустейна, наделенных по условиям завещания от Лероя П. Стила. В 1993 году AMS официально учредила три категории премии, две другие — это премия Лероя П. Стила за жизненные достижения и премия Лероя П. Стила за математическое изложение.

Премия Лероя П. Стила за выдающийся вклад в исследования, которая приносит денежный приз в размере 5000 долларов США, присуждается за статью, недавнюю или нет, которая доказала свою фундаментальную или непреходящую важность в своей области. Он имеет 6-летнюю ротацию предметных областей: открытость, анализ / вероятность, алгебра / теория чисел, прикладная математика, геометрия / топология и дискретная математика / логика. Издание 2022 г., выпущенное в знак признания «Улучшенных алгоритмов аппроксимации для задач максимального сокращения и выполнимости с использованием полуопределенного программирования», опубликовано в ноябре 1995 г. Журнал АКМ, был для прикладной математики. В настоящее время открыты номинации на статью по геометрии/топологии для издания 2023 года.

Согласно заявлению AMS:

Если вы никогда не сталкивались с проблемой Max-cut, ее очень легко сформулировать, но гораздо труднее доказать какую-либо гипотезу по этому поводу. Если у вас есть граф, т. е. сеть узлов и их соединений, задача Max-cut состоит в том, чтобы найти разрез, т. е. разбиение сети на два непересекающихся множества узлов, так что количество ребер, соединяющих две части, равно как можно больше. Другой способ думать об этом состоит в том, чтобы найти две части сети, которые максимально связаны. Эта абстрактная проблема не так уж абстрактна и имеет практическое применение в физике и схемотехнике.

Мишель Гуманс, который уже работал на математическом факультете Массачусетского технологического института в 1995 году и теперь возглавляет его, объяснил:

Наш ага-момент наступил в сентябре 1993 года, когда мы с Дэвидом подумали об использовании случайной гиперплоскости для округления решения нашей полуопределенной релаксации и, таким образом, получения доказуемо хороших разрезов графа совершенно (почти неловко) элементарным способом. Полуопределенная оптимизация теперь является классическим инструментом для аппроксимации широкого круга сложных алгоритмических задач, и я рад, что Дэвид и я сыграли свою роль в этом.

Дэвид Уильямсон был первым аспирантом Гумана, затем присоединился к IBM Research и с 2004 года является профессором Корнеллского университета. Он является соавтором книги «Разработка алгоритмов приближения». Он вспомнил:

Мишель и я разработали идею представления сечения векторами и сведения их к полуопределенной программе, когда я учился в аспирантуре. Но потом мы застряли на вопросе, как из векторов извлечь разрез, и отложили работу как минимум на год, пока я заканчивал диссертацию совсем по другой теме. Я сдал диссертацию и взял двухнедельный отпуск. По моему возвращению мы снова собрались по кусочкам и во время двухчасовой встречи однажды в пятницу днем ​​пришли к идее использования случайной гиперплоскости для разделения векторов. Вскоре последовал анализ основного результата.

Задача Max-cut является NP-трудной, поэтому любое точное полиномиальное решение будет означать, что P=NP. Поиск полиномиальных приближенных решений дает нам ключ к пониманию того, как можно найти точное полиномиальное решение, или проливает свет на то, почему это маловероятно.

Майк Джеймс является автором Руководство программиста по теории целью которой является представление фундаментальных идей информатики в неформальной, но информативной форме и Уловка разума: программирование и вычислительная мысль, в котором обсуждается, как думать о проблемах с точки зрения математики и программирования.

[ad_2] Source: i-programmer-info.com

Похожие статьи

Добавить комментарий

Ваш адрес email не будет опубликован.

Краткое описание по статье Премия AMS за алгоритм Max Cut

Название: Премия AMS за алгоритм Max Cut . Краткое описание: [ad_1] Мишель Гоэманс и Дэвид Уильямсон недавно получил . Дата публикации: 30.01.2022 . Автор: Алишер Валеев .

Для чего создан сайт Novosti-Nedeli.ru

Данный сайт посвящен новостям мира и мира технологий . Также тут вы найдете руководства по различным девайсам.

Сколько лет сайту?

Возраст составляет 3 года

Кнопка «Наверх»