WikiDer > Алан М. Фриз

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

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

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

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

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

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

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

Бумага^[1]это совместная работа Мартин Дайер, Алан Фриз и Равиндран Каннан.

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

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

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

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

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

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

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

Личная жизнь

Frieze женат на Кэрол Фриз, который руководит двумя информационными мероприятиями факультета информатики Университета Карнеги-Меллона.^[5]

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

внешняя ссылка

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