Alan M. Frieze - Alan M. Frieze

Alan M. Frieze (25 Ekim 1945'te doğdu Londra, İngiltere) Matematik Bilimleri Bölümü'nde profesördür. Carnegie Mellon Üniversitesi, Pittsburgh, Amerika Birleşik Devletleri. O mezun oldu Oxford Üniversitesi 1966'da doktora derecesini Londra Üniversitesi 1975'te. Araştırma ilgi alanları kombinatorik, ayrık optimizasyon ve teorik bilgisayar bilimi. Halen bu alanların olasılıksal yönlerine odaklanmaktadır; özellikle asimptotik özelliklerinin incelenmesi rastgele grafikler, algoritmaların ortalama durum analizi ve rastgele algoritmalar. Son çalışmaları şunları içeriyor: yaklaşık sayma ve aracılığıyla hacim hesaplaması rastgele yürüyüşler; içinde kenar ayrık yolları bulma genişletici grafikler ve keşfetmek anti-Ramsey teorisi ve istikrar yönlendirme algoritmaları.

Önemli katkılar

Alan Frieze tarafından yapılan iki önemli katkı:

(1) hacmini yaklaşık olarak belirlemek için polinom zaman algoritması dışbükey cisimler

(2) için algoritmik sürüm Szemerédi düzenlilik lemma

Bu algoritmaların her ikisi de burada kısaca açıklanacaktır.

Dışbükey cisimlerin hacmini tahmin etmek için polinom zaman algoritması

Kağıt^[1]ortak bir çalışmadır Martin Dyer, Alan Frieze ve Ravindran Kannan.

Makalenin ana sonucu, rasgele seçilmiş bir algoritmadır. ${ displaystyle epsilon}$ dışbükey cismin hacmine yaklaşıklık ${ displaystyle K}$ içinde ${ displaystyle n}$bir üyelik kahininin varlığını varsayarak boyutsal Öklid uzayı. Algoritma, bir polinom ile sınırlı zaman alır. ${ displaystyle n}$, boyutu ${ displaystyle K}$ ve ${ displaystyle 1 / epsilon}$.

Algoritma, sözde karmaşık bir kullanımıdır Markov zinciri Monte Carlo (MCMC) yöntemi: Algoritmanın temel şeması, içeriden neredeyse tekdüze bir örneklemedir. ${ displaystyle K}$ oluşan bir ızgara yerleştirerek nboyutlu küpler ve bu küplerin üzerinde rastgele bir yürüyüş yapmak. Teorisini kullanarakhızla karıştırılan Markov zincirleri, rastgele yürüyüşün neredeyse tekdüze bir dağılım haline gelmesinin polinom zamanını aldığını gösteriyorlar.

Szemerédi düzenlilik bölümü için algoritmik sürüm

Bu kağıt^[2]Alan Frieze'in birleşik çalışmasıdır ve Ravindran Kannan. Algoritmik versiyonunu türetmek için iki lema kullanırlar. Szemerédi düzenlilik lemma bulmak için ${ displaystyle epsilon}$-düzenli bölüm.

Lemma 1:
K'yi düzelt ve ${ displaystyle gamma}$ ve izin ver ${ displaystyle G = (V, E)}$ ile grafik olmak ${ displaystyle n}$ köşeler. İzin Vermek ${ displaystyle P}$ adil bir şekilde bölünmek ${ displaystyle V}$ sınıflarda ${ displaystyle V_ {0}, V_ {1}, ldots, V_ {k}}$. Varsaymak ${ displaystyle | V_ {1} |> 4 ^ {2k}}$ ve ${ displaystyle 4 ^ {k}> 600 gama ^ {2}}$. Daha fazla kanıt verildi ${ displaystyle gama k ^ {2}}$ çiftler ${ displaystyle (V_ {r}, V_ {s})}$ değiller ${ displaystyle gamma}$-düzenli, O (n) zamanında adil bir bölüm bulmak mümkündür ${ displaystyle P '}$ (hangi bir iyileştirmedir ${ displaystyle P}$) içine ${ displaystyle 1 + k4 ^ {k}}$ en fazla istisnai bir kardinalite sınıfına sahip sınıflar ${ displaystyle | V_ {0} | + n / 4 ^ {k}}$ ve bunun gibi ${ displaystyle operatorname {ind} (P ') geq operatorname {ind} (P) + gamma ^ {5} / 20}$

Lemma 2:
İzin Vermek ${ displaystyle W}$ olmak ${ displaystyle R times C}$ matris ile ${ displaystyle | R | = p}$, ${ displaystyle | C | = q}$ ve ${ displaystyle | W | _ { inf} leq 1}$ ve ${ displaystyle gamma}$ olumlu bir gerçek.
(a) Varsa ${ displaystyle S subseteq R}$, ${ displaystyle T subseteq C}$ öyle ki ${ displaystyle | S | geq gamma p}$, ${ displaystyle | T | geq gamma q}$ ve ${ displaystyle | W (S, T) | geq gamma | S || T |}$ sonra ${ displaystyle sigma _ {1} (W) geq gamma ^ {3} { sqrt {pq}}}$
(b) Eğer ${ displaystyle sigma _ {1} (W) geq gamma { sqrt {pq}}}$o zaman var ${ displaystyle S subseteq R}$, ${ displaystyle T subseteq C}$ öyle ki ${ displaystyle | S | geq gamma 'p}$, ${ displaystyle | T | geq gamma 'q}$ ve ${ Displaystyle W (S, T) geq gamma '| S || T |}$ nerede ${ displaystyle gamma '= gama ^ {3} / 108}$. Ayrıca, ${ displaystyle S}$, ${ displaystyle T}$ polinom zamanda inşa edilebilir.

Bu iki lema, aşağıdaki algoritmik yapıda birleştirilmiştir. Szemerédi düzenlilik lemma.

[Aşama 1] Köşelerini keyfi olarak bölün ${ displaystyle G}$ eşit bir bölüme ${ displaystyle P_ {1}}$ sınıflarla ${ displaystyle V_ {0}, V_ {1}, ldots, V_ {b}}$ nerede ${ displaystyle | V_ {i} | lfloor n / b rfloor}$ ve dolayısıyla ${ displaystyle | V_ {0} |$. belirtmek ${ displaystyle k_ {1} = b}$.
[Adım 2] Her çift için ${ displaystyle (V_ {r}, V_ {s})}$ nın-nin ${ displaystyle P_ {i}}$, hesaplamak ${ displaystyle sigma _ {1} (W_ {r, s})}$. Çifti ${ displaystyle (V_ {r}, V_ {s})}$ değiller ${ displaystyle epsilon -}$düzenli ve sonra Lemma 2 ile ${ displaystyle gamma = epsilon ^ {9} / 108-}$düzenli.
[Aşama 3] En fazla varsa ${ displaystyle epsilon sol ({ başlar {dizi} {c} k_ {1} 2 son {dizi}} sağ)}$ olmayan kanıtları üreten çiftler ${ displaystyle gamma -}$durduran düzenlilik. ${ displaystyle P_ {i}}$ dır-dir ${ displaystyle epsilon -}$düzenli.
[Adım 4] Lemma 1'i nereye uygulayın ${ displaystyle P = P_ {i}}$, ${ displaystyle k = k_ {i}}$, ${ displaystyle gamma = epsilon ^ {9} / 108}$ ve elde et ${ displaystyle P '}$ ile ${ displaystyle 1 + k_ {i} 4 ^ {k_ {i}}}$ sınıflar
[Adım 5] İzin Vermek ${ displaystyle k_ {i} + 1 = k_ {i} 4 ^ {k_ {i}}}$, ${ displaystyle P_ {i} + 1 = P '}$, ${ displaystyle i = i + 1}$ ve 2. Adıma gidin.

Ödüller ve onurlar

• 1991 yılında Frieze aldı (ortaklaşa Martin Dyer ve Ravi Kannan ) Fulkerson Ödülü Ayrık Matematik alanında, Amerikan Matematik Derneği ve Matematiksel Programlama Topluluğu. Ödül gazete içindi "Dışbükey cisimlerin hacmini tahmin etmek için rastgele bir polinom zaman algoritmasıJournal of the ACM'de).
• 1997'de Guggenheim bursiyeriydi.
• 2000 yılında IBM Fakülte Ortaklığı Ödülü'nü aldı.
• 2006 yılında ortaklaşa aldı ( Michael Krivelevich ABD-İsrail Binational Science Foundation'dan Profesör Pazy Memorial Araştırma Ödülü.
• 2011 yılında SIAM Fellow olarak seçildi.^[3]
• 2012'de AMS Üyesi seçildi.^[4]
• 2014 yılında bir Uluslararası Matematikçiler Kongresi'nde genel oturum Seul, Güney Kore'de.
• 2015 yılında Simons Fellow seçildi.

Kişisel hayat

Frieze ile evli Carol Frieze, Carnegie Mellon Üniversitesi'ndeki bilgisayar bilimleri bölümü için iki sosyal yardım girişimini yöneten.^[5]

Referanslar

Dış bağlantılar

• Alan Frieze'nin web sayfası
• Fulkerson ödüllü makale
• Alan Frieze'nin DBLP'deki yayınları
• Bazı kendi kendine arşivlenmiş eserler burada mevcuttur