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

Mostrar todas las versiones(3)

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 problema...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autor principal: Sáenz, Manuel
Otros Autores: Jonckheere, Matthieu Thimothy Samson
Formato: Tesis doctoral publishedVersion
Lenguaje:Español
Publicado: Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales 2019
Materias:
GRAFOS ALEATORIOS
OPTIMIZACION
PROCESOS ESTOCASTICOS
LIMITES DE ESCALA
RANDOM GRAPHS
CONFIGURATION MODEL
STOCHASTIC PROCESSES
SCALING LIMITS
Acceso en línea:https://hdl.handle.net/20.500.12110/tesis_n6964_Saenz
http://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=tesis_n6964_Saenz_oai
Aporte de:
Repositorio Digital de la Universidad de Buenos Aires (UBA) de Universidad de Buenos Aires
id I28-R145-tesis_n6964_Saenz_oai
record_format dspace
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-145
collection Repositorio Digital de la Universidad de Buenos Aires (UBA)
language Español
orig_language_str_mv spa
topic GRAFOS ALEATORIOS
OPTIMIZACION
PROCESOS ESTOCASTICOS
LIMITES DE ESCALA
RANDOM GRAPHS
CONFIGURATION MODEL
STOCHASTIC PROCESSES
SCALING LIMITS
spellingShingle GRAFOS ALEATORIOS
OPTIMIZACION
PROCESOS ESTOCASTICOS
LIMITES DE ESCALA
RANDOM GRAPHS
CONFIGURATION MODEL
STOCHASTIC PROCESSES
SCALING LIMITS
Sáenz, Manuel
Desempeño asintótico de algoritmos secuenciales en grafos aleatorios.
topic_facet GRAFOS ALEATORIOS
OPTIMIZACION
PROCESOS ESTOCASTICOS
LIMITES DE ESCALA
RANDOM GRAPHS
CONFIGURATION MODEL
STOCHASTIC PROCESSES
SCALING LIMITS
description 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.
author2 Jonckheere, Matthieu Thimothy Samson
author_facet Jonckheere, Matthieu Thimothy Samson
Sáenz, Manuel
format Tesis doctoral
Tesis doctoral
publishedVersion
author Sáenz, Manuel
author_sort Sáenz, Manuel
title Desempeño asintótico de algoritmos secuenciales en grafos aleatorios.
title_short Desempeño asintótico de algoritmos secuenciales en grafos aleatorios.
title_full Desempeño asintótico de algoritmos secuenciales en grafos aleatorios.
title_fullStr Desempeño asintótico de algoritmos secuenciales en grafos aleatorios.
title_full_unstemmed Desempeño asintótico de algoritmos secuenciales en grafos aleatorios.
title_sort desempeño asintótico de algoritmos secuenciales en grafos aleatorios.
publisher Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
publishDate 2019
url https://hdl.handle.net/20.500.12110/tesis_n6964_Saenz
http://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=tesis_n6964_Saenz_oai
work_keys_str_mv AT saenzmanuel desempenoasintoticodealgoritmossecuencialesengrafosaleatorios
AT saenzmanuel asymptoticperformanceofsequentialalgorithmsonrandomgraphs
_version_ 1766016056879480832
spelling I28-R145-tesis_n6964_Saenz_oai2023-04-26 Jonckheere, Matthieu Thimothy Samson Sáenz, Manuel 2019-11-19 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. In this thesis we study the evolution, convergence and optimality of search algorithms on random graphs through several examples and we use this analysis to give performance bounds of communication protocols for wireless networks. In particular, we study the following problems: - The determination of the asymptotic optimality of the degree-greedy algorithm in a broad class of Configuration Model graphs, and the computation of their independence ratios. Although the problem of finding maximum size independent sets is an NP-hard task, we show that on this class of random graphs the degree-greedy algorithm can construct asymptotically maximum independent sets taking just a polynomial time. We also use these results to characterise the independence ratio of certain Erdös-Rényi graphs and to give numerical procedures to compute upper bounds for general Configuration Model graphs. - The evaluation of the performance of variations of local greedy algorithms for approximating the capacity of WiFi networks and their possible impact on the fairness of the connection assignments. We use these results to study a real-world communication network: Montevideo’s cellphone antennas. - The computation of convergence times of best response algorithms for random distributed optimisation problems with actions structured as sparse random graphs. Using these results we prove, by means of an optimility lemma, general lower bounds for the running times of local search algorithms. Most of our results are set either on sparse Erdös-Rényi random graphs, Configuration Models or both, while the questions we deal with correspond to the asymptotic regime of large graph size. To analyse them, we use and extend existing results on the asymptotic sizes of various sub-graphs on random graph models; together with scaling limits and concentrations of random variables, to study the dynamics on them. The problems studied on this thesis resulted on three papers: [BJLS19][JS19b][JS19a]. The last of these still under preparation. Fil: Sáenz, Manuel. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. application/pdf https://hdl.handle.net/20.500.12110/tesis_n6964_Saenz spa Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales info:eu-repo/semantics/openAccess https://creativecommons.org/licenses/by-nc-sa/2.5/ar GRAFOS ALEATORIOS OPTIMIZACION PROCESOS ESTOCASTICOS LIMITES DE ESCALA RANDOM GRAPHS CONFIGURATION MODEL STOCHASTIC PROCESSES SCALING LIMITS Desempeño asintótico de algoritmos secuenciales en grafos aleatorios. Asymptotic performance of sequential algorithms on random graphs. info:eu-repo/semantics/doctoralThesis info:ar-repo/semantics/tesis doctoral info:eu-repo/semantics/publishedVersion http://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=tesis_n6964_Saenz_oai

Ejemplares similares