Grandes Desvíos para Procesos de Exploración de Grafos Aleatorios. (Defensa de Tesis Doctoral)

Director: Paola Bermolen Romeo

Codirector: Matthieu Jonckheere

RESUMEN

En esta tesis nos enfocamos en el estudio de los grandes desvíos (GD) para sucesiones de procesos de Markov que describen el comportamiento de ciertos algoritmos de exploración greedy sobre grafos aleatorios con el fin de construir conjuntos independientes en esos grafos.

Nos centramos en cuatro aspectos de los GD para estos procesos:

• Probar los GD para las trayectorias de dichos procesos de Markov,

• Deducir el límite fluido a partir de la función de tasa del GD,

• Encontrar la trayectoria que minimiza la función de tasa sobre un conjunto de trayectorias,

• Concluir resultados de GD para el tamaño del conjunto independiente construido mediante el algoritmo greedy.

Para demostrar el PGD (Principio de Grandes Desvíos) para las sucesiones de procesos de interés, utilizamos la estrategia propuesta por [Feng and Kurtz, 2006] para el estudio de GD de procesos estocásticos, la que se basa en la convergencia de semigrupos no lineales asociados a dichos procesos.

Además de presentar resultados originales sobre los GD para los procesos de interés, creemos que el aporte de este trabajo consiste en mostrar de forma entendible la herramienta poderosa propuesta en el trabajo de [Feng and Kurtz, 2006] para el estudio de GD de procesos, con posibles aplicaciones a diversas áreas.