Seminario de Probabilidad y Estadística
Título: Algoritmos online de matching para el Stochastic Block Model
Expositor: Nahuel Soprano Loto (LAAS, Toulouse, Francia)
Resumen: Un matching en un grafo es un conjunto de aristas que no comparten extremos. Desarrollar algoritmos que encuentren matchings grandes es un problema importante. Un algoritmo se dice online si tiene que construir el matching paso a paso a medida que el grafo se va "descubriendo". Los algoritmos online han recibido gran atención en los últimos años debido a su extensa aplicabilidad (mercados de trabajo, anuncios en internet, etc.). Nosotros estudiamos algoritmos online en el Stochastic Block Model (SBM), un modelo clásico de grafo aleatorio en el que los vértices tienen clases, y dos vértices son adyacentes o no de acuerdo a una probabilidad que depende de las clases involucradas. Estudiamos el caso denso, es decir, en el que las probabilidades de adyacencia no escalan con el tamaño del grafo. En este contexto, demostramos que existe una transición de fase en la performance de los algoritmos online regida por una condición, llamada NCOND en la literatura, que depende de las probabilidades de adyacencia del SBM.
Es un trabajo en colaboración con Matthieu Jonckheere y Pascal Moyal.
Viernes 24/3 a las 10:30
zoom
Contacto: Alejandro Cholaquidis - acholaquidis@hotmail.com
Link:
https://salavirtual-udelar.zoom.us/j/88544669179?pwd=UlBHdWRWdEZVMGw0ak…
Página del seminario: https://pye.cmat.edu.uy/seminario
Página del grupo: https://pye.cmat.edu.uy/home
Canal de youtube: https://www.youtube.com/channel/UCOPZEOrLSAYPz2qCAL-KqMg/about