Алан М. Фриз - Alan M. Frieze

Алан М. Фриз (родился 25 октября 1945 года в Лондоне , Англия), профессор кафедры математических наук Университета Карнеги-Меллона , Питтсбург , США. Он окончил Оксфордский университет в 1966 году и получил докторскую степень в Лондонском университете в 1975 году. Его исследовательские интересы лежат в области комбинаторики , дискретной оптимизации и теоретической информатики . В настоящее время он сосредотачивается на вероятностных аспектах этих областей; в частности, изучение асимптотических свойств случайных графов , анализ среднего случая алгоритмов и рандомизированных алгоритмов . Его недавняя работа включала приблизительный подсчет и вычисление объема с помощью случайных блужданий ; поиск непересекающихся ребер путей в расширительных графах , а также изучение теории анти-Рамсея и стабильности алгоритмов маршрутизации .

Ключевые вклады

Два ключевых вклада Алана Фриза:

(1) полиномиальный алгоритм аппроксимации объема выпуклых тел.

(2) алгоритмическая версия леммы Семереди о регулярности

Оба этих алгоритма будут кратко описаны здесь.

Алгоритм полиномиального времени для аппроксимации объема выпуклых тел

Статья является совместной работой Мартина Дайера , Алана Фриза и Равиндрана Каннана .

Основным результатом статьи является рандомизированный алгоритм поиска приближения к объему выпуклого тела в -мерном евклидовом пространстве, предполагая существование оракула членства. Алгоритм требует времени, ограниченного полиномом от размерности и . ${\ displaystyle \ epsilon}$${\ displaystyle K}$${\ displaystyle n}$${\ displaystyle n}$${\ displaystyle K}$${\ displaystyle 1 / \ epsilon}$

Алгоритм представляет собой сложное использование так называемого метода Монте-Карло цепи Маркова (MCMC). Основная схема алгоритма - это почти однородная выборка изнутри путем размещения сетки, состоящей из n -мерных кубов, и выполнения случайного обхода этих кубов. Используя теорию быстрого перемешивания цепей Маркова , они показывают, что случайному блужданию требуется полиномиальное время, чтобы оно стало почти однородным распределением. ${\ displaystyle K}$

Алгоритмический вариант разбиения регулярности Семереди

Эта статья является совместной работой Алана Фриза и Равиндрана Каннана . Они используют две леммы для вывода алгоритмической версии леммы Семереди о регулярности для нахождения -регулярного разбиения. ${\ displaystyle \ epsilon}$

Лемма 1:
Зафиксируем k и и пусть - граф с вершинами. Позвольте быть равным разделением на классы . Допустим и . Имея доказательства того, что более чем пары не являются -регулярными, можно найти за O (n) время справедливое разбиение (которое является уточнением ) на классы с исключительным классом мощности не более чем и таким, что ${\ displaystyle \ gamma}$${\ Displaystyle G = (V, E)}$${\ displaystyle n}$${\ displaystyle P}$${\ displaystyle V}$${\ Displaystyle V_ {0}, V_ {1}, \ ldots, V_ {k}}$${\ displaystyle | V_ {1} |> 4 ^ {2k}}$${\ displaystyle 4 ^ {k}> 600 \ gamma ^ {2}}$${\ Displaystyle \ гамма к ^ {2}}$${\ displaystyle (V_ {r}, V_ {s})}$${\ displaystyle \ gamma}$${\ displaystyle P '}$${\ displaystyle P}$${\ displaystyle 1 + k4 ^ {k}}$${\ displaystyle | V_ {0} | + n / 4 ^ {k}}$${\ displaystyle \ operatorname {ind} (P ') \ geq \ operatorname {ind} (P) + \ gamma ^ {5} / 20}$

Лемма 2:
Пусть будет матрица , а и быть положительным реальным. (а) Если существует , таким образом, что , и затем (б) Если , то существует , например , что , и где . Кроме того, , могут быть построены в полиномиальное время. ${\ displaystyle W}$${\ Displaystyle R \ раз C}$${\ displaystyle | R | = p}$${\ displaystyle | C | = q}$${\ Displaystyle \ | W \ | _ {\ inf} \ Leq 1}$${\ displaystyle \ gamma}$
${\ Displaystyle S \ substeq R}$${\ displaystyle T \ substeq C}$${\ displaystyle | S | \ geq \ gamma p}$${\ displaystyle | T | \ geq \ gamma q}$${\ Displaystyle | W (S, T) | \ geq \ gamma | S || T |}$${\ displaystyle \ sigma _ {1} (W) \ geq \ gamma ^ {3} {\ sqrt {pq}}}$
${\ displaystyle \ sigma _ {1} (W) \ geq \ gamma {\ sqrt {pq}}}$${\ Displaystyle S \ substeq R}$${\ displaystyle T \ substeq C}$${\ Displaystyle | S | \ geq \ gamma 'p}$${\ displaystyle | T | \ geq \ gamma 'q}$${\ Displaystyle W (S, T) \ geq \ gamma '| S || T |}$${\ displaystyle \ gamma '= \ gamma ^ {3} / 108}$${\ displaystyle S}$${\ displaystyle T}$

Эти две леммы объединены в следующей алгоритмической конструкции леммы Семереди о регулярности .

[Шаг 1] Произвольно разделите вершины на равное разделение с классами где и, следовательно . обозначают . [Стади 2] Для каждой пары из вычислите . Если пара не регулярна, то по лемме 2 мы получаем доказательство того, что они не регулярны. [Шаг 3] Если имеется не больше пар, дающих доказательства нерегулярности, то они останавливаются. является регулярным. [Шаг 4] Применим лемму 1 , где , , и получить с классами [Шаг 5] Пусть , , и перейдите к шагу 2. ${\ displaystyle G}$${\ Displaystyle P_ {1}}$${\ Displaystyle V_ {0}, V_ {1}, \ ldots, V_ {b}}$${\ Displaystyle | V_ {i} | \ lfloor n / b \ rfloor}$${\ displaystyle | V_ {0} | <b}$${\ displaystyle k_ {1} = b}$
${\ displaystyle (V_ {r}, V_ {s})}$${\ displaystyle P_ {i}}$${\ displaystyle \ sigma _ {1} (W_ {r, s})}$${\ displaystyle (V_ {r}, V_ {s})}$${\ displaystyle \ epsilon -}$${\ displaystyle \ gamma = \ epsilon ^ {9} / 108-}$
${\ displaystyle \ epsilon \ left ({\ begin {array} {c} k_ {1} \\ 2 \\\ end {array}} \ right)}$${\ displaystyle \ gamma -}$${\ displaystyle P_ {i}}$${\ displaystyle \ epsilon -}$
${\ displaystyle P = P_ {i}}$${\ displaystyle k = k_ {i}}$${\ displaystyle \ gamma = \ epsilon ^ {9} / 108}$${\ displaystyle P '}$${\ displaystyle 1 + k_ {i} 4 ^ {k_ {i}}}$
${\ Displaystyle к_ {я} + 1 = к_ {я} 4 ^ {к_ {я}}}$${\ displaystyle P_ {i} + 1 = P '}$${\ Displaystyle я = я + 1}$

Награды и награды

• В 1991 году Фриз получил (совместно с Мартином Дайером и Рави Каннаном ) премию Фулкерсона по дискретной математике, присуждаемую Американским математическим обществом и Обществом математического программирования . Награда была присуждена за статью « Алгоритм случайного полиномиального времени для аппроксимации объема выпуклых тел » в журнале ACM).
• В 1997 году он был научным сотрудником Гуггенхайма.
• В 2000 году он получил награду IBM Faculty Partnership Award.
• В 2006 году он совместно с Майклом Кривелевичем получил премию за научные исследования памяти профессора Пази от США-Израильского фонда бинациональных исследований.
• В 2011 году он был выбран в качестве стипендиата SIAM.
• В 2012 году он был выбран в качестве стипендиата AMS.
• В 2014 году он выступил с пленарным докладом на Международном математическом конгрессе в Сеуле, Южная Корея.
• В 2015 году он был выбран в качестве стипендиата Simons.

Личная жизнь

Фриз женат на Кэрол Фриз , которая руководит двумя информационно-просветительскими работами на факультете информатики в Университете Карнеги-Меллона.

Рекомендации

Внешние ссылки

• Веб-страница Алана Фриза
• Работа, удостоенная премии Фулкерсона
• Публикации Алана Фриза в DBLP
• Некоторые самоархивированные работы доступны здесь.