Pasar al contenido principal

Algoritmos online de matching para el Stochastic Block Model

Fecha de inicio
Fecha de fin

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 [at] hotmail.com (acholaquidis[at]hotmail[dot]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