Alan M. Frieze

Alan M. Frieze (Geboren am 25. Oktober 1945 in London, England) ist Professor in der Abteilung für Mathematikwissenschaften unter Carnegie Mellon Universität, Pittsburgh, Vereinigte Staaten. Er absolvierte die Universität von Oxford 1966 und erhielt seinen Doktortitel vor dem Universität von London 1975. Seine Forschungsinteressen liegen in Kombinatorik, Diskrete Optimierung und Theoretische Informatik. Derzeit konzentriert er sich auf die probabilistischen Aspekte dieser Bereiche. insbesondere die Untersuchung der asymptotischen Eigenschaften von Zufällige Grafiken, die durchschnittliche Fallanalyse von Algorithmen und Randomisierte Algorithmen. Seine jüngsten Arbeiten umfassten ungefähre Zähl- und Volumenberechnung über Zufällige Spaziergänge; Finden von Randdisjunkt -Pfaden in Expander -Diagrammeund Erforschung der Anti-Ramsey-Theorie und der Stabilität von Routing -Algorithmen.

Schlüsselbeiträge

Zwei wichtige Beiträge von Alan Frieze sind:

(1) Polynomzeitalgorithmus zur Annäherung an das Volumen von konvexe Körper

(2) algorithmische Version für Szemerédi Regelmäßigkeit Lemma

Beide Algorithmen werden hier kurz beschrieben.

Polynomzeitalgorithmus zur Annäherung des Volumens konvexer Körper

Das Papier[1] ist eine gemeinsame Arbeit von Martin DyerAlan Frieze und Ravindran Kannan.

Das Hauptergebnis des Papiers ist ein randomisierter Algorithmus zum Finden eines Annäherung an das Volumen eines konvexen Körpers in -Dimensionaler euklidischer Raum durch die Existenz eines Mitglieds -Orakels. Der Algorithmus nimmt die Zeit, die durch ein Polynom in der In -in begrenzt ist , die Dimension von und .

Der Algorithmus ist eine raffinierte Verwendung der sogenannten Verwendung Markov -Kette Monte Carlo (MCMC) Methode. Das Grundschema des Algorithmus ist eine nahezu einheitliche Stichprobe von innen durch Platzierung eines Gitters bestehend n-Dimensionale Würfel und einen zufälligen Spaziergang über diese Würfel. Durch Verwendung der Theorie vonschnell mischen Markov -KettenSie zeigen, dass es eine Polynomzeit braucht, bis der zufällige Spaziergang eine nahezu einheitliche Verteilung ist.

Algorithmische Version für Szemerédi -Regelmäßigkeitspartition

Dieses Papier[2] ist eine kombinierte Arbeit von Alan Frieze und Ravindran Kannan. Sie verwenden zwei Lemmas, um die algorithmische Version der abzuleiten Szemerédi Regelmäßigkeit Lemma um einen zu finden -reguläre Partition.


Lemma 1:
Reparieren k und und lass ein Diagramm sein mit Eckpunkte. Lassen eine gerechte Partition von sein in Klassen . Davon ausgehen und . Gegebener Beweise, die mehr als Paare sind nicht -regulär ist es möglich, in o (n) Zeit eine gerechte Partition zu finden (was eine Verfeinerung von ist ) hinein Klassen mit einer außergewöhnlichen Klasse von Kardinalität höchstens und so das


Lemma 2:
Lassen sei a Matrix mit , und und Sei positiv real.
(a) Wenn es existiert , so dass , und dann
(b) wenn dann gibt es da , so dass , und wo . Außerdem, , kann in Polynomzeit konstruiert werden.


Diese beiden Lemmas werden in der folgenden algorithmischen Konstruktion der kombiniert Szemerédi Regelmäßigkeit Lemma.


[Schritt 1] Willkürlich die Eckpunkte von teilen in eine gerechte Partition mit Klassen wo und daher . bezeichnen .
[Schritt 2] Für jedes Paar von , berechnen . Wenn das Paar sind nicht Regelmäßig von Lemma 2 erhalten wir einen Beweis dafür, dass sie es nicht sind regulär.
[Schritt 3] Wenn es höchstens gibt Paare, die Beweise von Non erzeugen Regelmäßigkeit, die anhalten. ist regulär.
[Schritt 4] Lemma 1 wo auftragen , , und erhalten mit Klassen
[Schritt 5] Lassen , , und gehen Sie zu Schritt 2.

Auszeichnungen und Ehrungen

Persönliches Leben

Frieze ist verheiratet mit Carol Frieze, der zwei Öffentlichkeitsarbeit für die Informatikabteilung der Carnegie Mellon University leitet.[5]

Verweise

  1. ^ M.Dyer, A.Frize und R.Kannan (1991). "Ein zufälliger Polynom-Zeit-Algorithmus zur Annäherung an das Volumen konvexer Körper". Journal of the ACM. Vol. 38, nein. 1. S. 1–17.
  2. ^ A.Frize und R.Kannan (1999). "Ein einfacher Algorithmus zum Bau von Szemere'di -Regelmäßigkeitspartition" (PDF). Elektron. J. ComM. Vol. 6.
  3. ^ Siam Fellows Klasse von 2011
  4. ^ Liste der Stipendiaten der American Mathematical Society, abgerufen am 29. Dezember 2012.
  5. ^ Frieze, Carol, persönlich, Carnegie Mellon Universität, abgerufen 20. Januar 2019

Externe Links