Desempeño asintótico de algoritmos secuenciales en grafos aleatorios.

Institución otorgante:

Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales

Fecha:

2019-11-19

Tipo de documento: 

info:eu-repo/semantics/doctoralThesis
 

Formato:

application/pdf

Idioma:

spa

Temas:

GRAFOS ALEATORIOS - OPTIMIZACION - PROCESOS ESTOCASTICOS - LIMITES DE ESCALA - RANDOM GRAPHS - CONFIGURATION MODEL - STOCHASTIC PROCESSES - SCALING LIMITS

Descripción:

En esta tesis estudiamos la evolución, convergencia y optimalidad de algoritmos de búsqueda en grafos aleatorios a través de ejemplos y aplicamos estos resultados al estudio de cotas de desempeño para protocolos de comunicación en redes inalámbricas. En particular, estudiamos los siguientes problemas: - La determinación de la optimalidad asintótica del algoritmo grado-egoísta en una amplia clase de Modelos de Configuraciones y el computo de sus respectivos cocientes de independencia. Aunque el problema de hallar conjuntos independientes de tamaño máximo es en el caso general una tarea NP-difícil, mostramos que en cierta clase de grafos aleatorios el algoritmo grado egoísta construye conjuntos independientes asintóticamente máximos en tiempo polinomial. Además, utilizamos estos resultados para caracterizar el cociente de independencia de grafos de Erdös-Rényi (de grado medio menor a e) y para encontrar procedimientos numéricos que permitan calcular cotas superiores en Modelos de Configuraciones generales. - La evaluación del desempeño de variantes locales del algoritmo egoísta aplicados al problema de aproximar la capacidad de redes WiFi y su posible impacto en la justicia de la distribución de conexiones. Por otro lado, aplicamos estos resultados al estudio de una red de comunicación empírica: el sistema de antenas de celulares de Montevideo. - El cálculo de los tiempos de convergencia para algoritmos de respuesta óptima en problemas de optimización distribuida donde las acciones se estructuran como grafos aleatorios ralos. Usando estos resultados probamos, por medio de un lema de optimalidad, cotas inferiores generales para los tiempos de corrida de algoritmos locales de búsqueda. La mayoría de nuestros resultados son aplicados tanto a grafos de Erdös-Rényi como a Modelos de Configuraciones y se centran en el régimen asintótico de grafos grandes. Para establecerlos utilizamos y extendemos teoremas existentes sobre los tamaños asintóticos de ciertos sub-grafos en modelos de grafos aleatorios, junto con límites de escala y concentraciones de variables aleatorios para estudiar las dinámicas en ellos. Los problemas estudiados en esta tesis resultaron en los siguientes tres trabajos: [BJLS19][JS19b][JS19a]. De los cuales el último se encuentra aún en preparación.

Identificador:

https://hdl.handle.net/20.500.12110/tesis_n6964_Saenz