Alan M. Frieze (nacido el 25 de octubre de 1945 en Londres , Inglaterra) es profesor en el Departamento de Ciencias Matemáticas de la Universidad Carnegie Mellon , Pittsburgh , Estados Unidos. Se graduó de la Universidad de Oxford en 1966 y obtuvo su doctorado en la Universidad de Londres en 1975. Sus intereses de investigación se centran en la combinatoria , la optimización discreta y la informática teórica . Actualmente, se centra en los aspectos probabilísticos de estas áreas; en particular, el estudio de las propiedades asintóticas de gráficos aleatorios , el análisis de caso promedio de algoritmos yalgoritmos aleatorios . Su trabajo reciente ha incluido el recuento aproximado y el cálculo del volumen mediante paseos aleatorios ; encontrar caminos disjuntos de borde en gráficos expansores y explorar la teoría anti-Ramsey y la estabilidad de los algoritmos de enrutamiento .
Contribuciones clave
Dos contribuciones clave hechas por Alan Frieze son:
(1) algoritmo de tiempo polinomial para aproximar el volumen de cuerpos convexos
(2) versión algorítmica para el lema de regularidad de Szemerédi
Ambos algoritmos se describirán brevemente aquí.
Algoritmo de tiempo polinomial para aproximar el volumen de cuerpos convexos
El artículo [1] es un trabajo conjunto de Martin Dyer , Alan Frieze y Ravindran Kannan .
El resultado principal del artículo es un algoritmo aleatorio para encontrar un aproximación al volumen de un cuerpo convexo en -Espacio euclidiano dimensional por asumir la existencia de un oráculo de pertenencia. El algoritmo toma un tiempo limitado por un polinomio en, la dimensión de y .
El algoritmo es un uso sofisticado del llamado método Monte Carlo de cadena de Markov (MCMC). El esquema básico del algoritmo es un muestreo casi uniforme desde dentrocolocando una cuadrícula que consta de cubos n- dimensionales y haciendo una caminata aleatoria sobre estos cubos. Al utilizar la teoría de la mezcla rápida de cadenas de Markov , muestran que se necesita un tiempo polinomial para que el recorrido aleatorio se establezca en una distribución casi uniforme.
Versión algorítmica para la partición de regularidad de Szemerédi
Este artículo [2] es un trabajo combinado de Alan Frieze y Ravindran Kannan . Usan dos lemas para derivar la versión algorítmica del lema de regularidad de Szemerédi para encontrar un-partición regular.
Lema 1:
Corrija k y y deja ser un gráfico con vértices. Dejar ser una partición equitativa de en clases . Asumir y . Dadas las pruebas de que más de pares no son -regular, es posible encontrar en O (n) tiempo una partición equitativa (que es un refinamiento de ) dentro clases, con una clase excepcional de cardinalidad como mucho y tal que
Lema 2:
Sea ser un matriz con , y y sea un real positivo.
(a) Si existen, tal que , y luego
(b) Si , entonces existen , tal que , y dónde . Además,, se puede construir en tiempo polinomial.
Estos dos lemas se combinan en la siguiente construcción algorítmica del lema de regularidad de Szemerédi .
[Paso 1] Divide arbitrariamente los vértices de en una partición equitativa con clases dónde y por lo tanto . denotar.
[Paso 2] Para cada par de , calcular . Si el par no son regular entonces por el Lema 2 obtenemos una prueba de que no son regular.
[Paso 3] Si hay como máximo pares que producen pruebas de no regularidad que se detiene. es regular.
[Paso 4] Aplique el Lema 1 donde, , y obtener con clases
[Paso 5] Deje, , y vaya al paso 2.
Premios y honores
- En 1991, Frieze recibió (junto con Martin Dyer y Ravi Kannan ) el Premio Fulkerson en Matemáticas Discretas otorgado por la American Mathematical Society y la Mathematical Programming Society . El premio fue para el trabajo " Un algoritmo de tiempo polinomial aleatorio para aproximar el volumen de cuerpos convexos " en la Revista de la ACM).
- En 1997 fue becario Guggenheim.
- En 2000, recibió el premio IBM Faculty Partnership Award.
- En 2006 recibió conjuntamente (con Michael Krivelevich ) el Premio de Investigación en Memoria del Profesor Pazy de la Fundación Binacional de Ciencias Estados Unidos-Israel.
- En 2011 fue seleccionado como becario SIAM. [3]
- En 2012 fue seleccionado como AMS Fellow. [4]
- En 2014 dio una charla plenaria en el Congreso Internacional de Matemáticos en Seúl, Corea del Sur.
- En 2015 fue seleccionado como Simons Fellow.
Vida personal
Frieze está casado con Carol Frieze , quien dirige dos esfuerzos de divulgación para el departamento de ciencias de la computación en la Universidad Carnegie Mellon. [5]
Referencias
- ^ M. Dyer, A. Frieze y R. Kannan (1991). "Un algoritmo de tiempo polinomial aleatorio para aproximar el volumen de cuerpos convexos" . Revista de la ACM . 38 (1). págs. 1-17.
- ^ A. Frieze y R. Kannan (1999). "Un algoritmo simple para construir la partición de regularidad de Szemere'di" (PDF) . Electrón. J. Comb . 6 .
- ^ Clase de becarios de Siam de 2011
- ^ Lista de miembros de la American Mathematical Society , consultado el 29 de diciembre de 2012.
- ^ Frieze, Carol, Personal , Carnegie Mellon University , consultado el 20 de enero de 2019