Alan M. Frieze - Alan M. Frieze

Alan M. Frieze (narozen 25. října 1945 v Londýn, Anglie) je profesorem na Katedře matematických věd v Univerzita Carnegie Mellon, Pittsburgh, Spojené státy. Vystudoval University of Oxford v roce 1966 a doktorát získal na University of London v roce 1975. Jeho výzkumné zájmy spočívají v kombinatorika, diskrétní optimalizace a teoretická informatika. V současné době se zaměřuje na pravděpodobnostní aspekty těchto oblastí; zejména studium asymptotických vlastností náhodné grafy průměrná případová analýza algoritmů a randomizované algoritmy. Jeho nedávná práce zahrnovala přibližné počítání a výpočet objemu pomocí náhodné procházky; hledání hranových disjunktních cest ve Windows expandérové ​​grafy a zkoumat anti-Ramseyova teorie a stabilita směrovací algoritmy.

Klíčové příspěvky

Dva klíčové příspěvky od Alana Frieze jsou:

(1) algoritmus polynomiálního času pro aproximaci objemu konvexní těla

(2) algoritmická verze pro Szemerédiho pravidelnost lemma

Oba tyto algoritmy zde budou stručně popsány.

Polynomiální časový algoritmus pro aproximaci objemu konvexních těles

Papír^[1]je společným dílem Martin Dyer, Alan Frieze a Ravindran Kannan.

Hlavním výsledkem příspěvku je randomizovaný algoritmus pro nalezení ${ displaystyle epsilon}$ aproximace objemu konvexního těla ${ displaystyle K}$ v ${ displaystyle n}$-dimenzionální euklidovský prostor předpokládáním existence věštby členství. Algoritmus vyžaduje čas ohraničený polynomem v ${ displaystyle n}$, rozměr ${ displaystyle K}$ a ${ displaystyle 1 / epsilon}$.

Algoritmus je sofistikované využití tzv Markovský řetězec Monte Carlo Metoda (MCMC). Základní schéma algoritmu je téměř jednotné vzorkování zevnitř ${ displaystyle K}$ umístěním mřížky sestávající n-dimenzionální kostky a náhodná procházka těmito kostkami. Použitím teorierychle míchající Markovovy řetězce, ukazují, že náhodné procházce trvá polynomiální čas, než se usadí na téměř rovnoměrném rozdělení.

Algoritmická verze pro pravidelný oddíl Szemerédi

Tento papír^[2]je kombinovaným dílem Alana Frieze a Ravindran Kannan. K odvození algoritmické verze Szemerédiho pravidelnost lemma najít ${ displaystyle epsilon}$-pravidelný oddíl.

Lemma 1:
Opravte k a ${ displaystyle gamma}$ a nechte ${ displaystyle G = (V, E)}$ být graf s ${ displaystyle n}$ vrcholy. Nechat ${ displaystyle P}$ být spravedlivým oddílem ${ displaystyle V}$ ve třídách ${ displaystyle V_ {0}, V_ {1}, ldots, V_ {k}}$. Převzít ${ displaystyle | V_ {1} |> 4 ^ {2k}}$ a ${ displaystyle 4 ^ {k}> 600 gama ^ {2}}$. Dané důkazy, že více než ${ displaystyle gamma k ^ {2}}$ páry ${ displaystyle (V_ {r}, V_ {s})}$ nejsou ${ displaystyle gamma}$-pravidelný, je možné najít v O (n) čase spravedlivý oddíl ${ displaystyle P '}$ (což je upřesnění ${ displaystyle P}$) do ${ displaystyle 1 + k4 ^ {k}}$ třídy, s výjimečnou třídou mohutnosti nanejvýš ${ displaystyle | V_ {0} | + n / 4 ^ {k}}$ a takhle ${ displaystyle operatorname {ind} (P ') geq operatorname {ind} (P) + gamma ^ {5} / 20}$

Lemma 2:
Nechat ${ displaystyle W}$ být ${ displaystyle R krát C}$ matice s ${ displaystyle | R | = p}$, ${ displaystyle | C | = q}$ a ${ displaystyle | W | _ { inf} leq 1}$ a ${ displaystyle gamma}$ být pozitivní skutečný.
a) Pokud existují ${ displaystyle S subseteq R}$, ${ displaystyle T subseteq C}$ takhle ${ displaystyle | S | geq gamma p}$, ${ displaystyle | T | geq gamma q}$ a ${ displaystyle | W (S, T) | geq gamma | S || T |}$ pak ${ displaystyle sigma _ {1} (W) geq gamma ^ {3} { sqrt {pq}}}$
(b) Pokud ${ displaystyle sigma _ {1} (W) geq gamma { sqrt {pq}}}$, pak existují ${ displaystyle S subseteq R}$, ${ displaystyle T subseteq C}$ takhle ${ displaystyle | S | geq gamma 'p}$, ${ displaystyle | T | geq gamma 'q}$ a ${ displaystyle W (S, T) geq gamma '| S || T |}$ kde ${ displaystyle gamma '= gamma ^ {3} / 108}$. Dále ${ displaystyle S}$, ${ displaystyle T}$ lze sestrojit v polynomiálním čase.

Tato dvě lemata jsou kombinována v následující algoritmické konstrukci Szemerédiho pravidelnost lemma.

[Krok 1] Libovolně rozdělte vrcholy ${ displaystyle G}$ do spravedlivého oddílu ${ displaystyle P_ {1}}$ s třídami ${ displaystyle V_ {0}, V_ {1}, ldots, V_ {b}}$ kde ${ displaystyle | V_ {i} | lfloor n / b rfloor}$ a tudíž ${ displaystyle | V_ {0} |$. označit ${ displaystyle k_ {1} = b}$.
[Krok 2] Pro každý pár ${ displaystyle (V_ {r}, V_ {s})}$ z ${ displaystyle P_ {i}}$, vypočítat ${ displaystyle sigma _ {1} (W_ {r, s})}$. Pokud pár ${ displaystyle (V_ {r}, V_ {s})}$ nejsou ${ displaystyle epsilon -}$pravidelně pak u Lemmy 2 získáme důkaz, že nejsou ${ displaystyle gamma = epsilon ^ {9} / 108-}$pravidelný.
[Krok 3] Pokud jich je nanejvýš ${ displaystyle epsilon left ({ begin {array} {c} k_ {1} 2 end {array}} right)}$ páry, které produkují důkazy o ne ${ displaystyle gamma -}$pravidelnost se zastaví. ${ displaystyle P_ {i}}$ je ${ displaystyle epsilon -}$pravidelný.
[Krok 4] Aplikujte Lemma 1 kde ${ displaystyle P = P_ {i}}$, ${ displaystyle k = k_ {i}}$, ${ displaystyle gamma = epsilon ^ {9} / 108}$ a získat ${ displaystyle P '}$ s ${ displaystyle 1 + k_ {i} 4 ^ {k_ {i}}}$ třídy
[Krok 5] Nechat ${ displaystyle k_ {i} + 1 = k_ {i} 4 ^ {k_ {i}}}$, ${ displaystyle P_ {i} + 1 = P '}$, ${ displaystyle i = i + 1}$ a přejděte ke kroku 2.

Ocenění a vyznamenání

• V roce 1991 obdržel Frieze (společně s Martin Dyer a Ravi Kannan ) Fulkersonova cena v diskrétní matematice udělené Americká matematická společnost a Společnost pro matematické programování. Ocenění bylo za papír „Náhodný algoritmus polynomiálního času pro přiblížení objemu konvexních těles"ve Věstníku ACM).
• V roce 1997 působil jako Guggenheim Fellow.
• V roce 2000 obdržel cenu IBM Faculty Partnership Award.
• V roce 2006 společně obdržel (s Michael Krivelevich ) Cena profesora Pazyho Memorial Research Award od USA-Izraele Binational Science Foundation.
• V roce 2011 byl vybrán jako pracovník SIAM.^[3]
• V roce 2012 byl vybrán jako člen AMS.^[4]
• V roce 2014 dal a plenární přednáška na Mezinárodním kongresu matematiků v Soulu v Jižní Koreji.
• V roce 2015 byl vybrán jako Simons Fellow.

Osobní život

Frieze je ženatý Carol Frieze, který řídí dvě terénní úsilí pro oddělení výpočetní techniky na Carnegie Mellon University.^[5]

Reference

externí odkazy

• Webová stránka Alana Frieze
• Fulkerson oceněný papír
• Publikace Alana Frieze na DBLP
• Některá samostatně archivovaná díla jsou k dispozici zde