Defenses

Grandes desvíos para procesos de exploración de grafos aleatorios

student: Valeria Goicoechea Jackson


Share:

El Área de Matemática del PEDECIBA invita a la defensa de tesis de doctorado de la estudiante  Valeria Goicoechea Jackson.

Orientadores:

Dra.Paola Bermolen
Dr. Matthieu Jonckheere

Integración del tribunal:


Dra. Paola Bermolen
Dra. Karine Bertin
Dr. Pablo Groisman
Dr. José R. León
Dr. Alain Roualt

Resumen de la tesis

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 & 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.
La tesis se desarrolla de la siguiente manera. Comenzamos presentando brevemente el trabajo de [Feng & Kurtz, 2006] en el contexto de procesos de Markov sobre espacios de estados compactos. En el Capítulo 3, analizamos los cuatro aspectos de los GD mencionados antes para una sucesión de procesos de Markov relacionados a un algoritmo greedy definido sobre un grafo de Erdös-Rényi dado con el objetivo de construir un conjunto independiente, cuando el tamaño del grafo tiene a infinito. En el Capitulo 4, repetimos este análisis para un algoritmo en el que simultáneamente se construye un grafo d-regular y un conjunto independiente en ese grafo. Finalmente, en el Capítulo 5 extendemos los resultados del capitulo anterior para grafos aleatorios uniformes más generales.
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 & Kurtz, 2006] para el estudio de GD de procesos, con posibles aplicaciones a diversas áreas.

Institutions:

IMERL, Facultad de Ingeniería

Place:

Salón de Seminarios IMERL-Facultad de Ingeniería

Date:

06/05/2022

Hour:

10:30

Defensas recientes

"Estructurantes alternativos obtenidos a partir de subproductos de la industria nacional para la elaboración de oleogeles destinados a la industria alimentaria"

"Efectos de la actividad forestal sobre la diversidad taxonómica y funcional de la comunidad de hormigas epigeicas de Uruguay "

"Sobre los horizontes de Cauchy compactos: un teorema de clasificación topológica y nulo-orbital"