[Probabilidad-Estadistica-Seminario] Seminario de Probabilidad y Estad�stica -- Viernes 11 de setiembre

[Andr�s Sosa]

Hola a todos

Este viernes 11 de setiembre a las 10:00 horas en el *Complejo Cultural
Muralla Abierta, Museo de las Migraciones*, Bartolom� Mitre 1550
hablar�* Marcelo
Fiori *(IMERL, Facultad de Ingenier�a) en el seminario de Probabilidad y
Estad�stica.

El t�tulo de la charla es: *Problemas de Graph Matching: resultados
probabil�sticos y determin�sticos.*

Saludos
Andr�s

*Abstract:*

*Dados dos grafos, el problema denominado Graph Matching Problem consiste
en encontrar el mejor alineamiento entre ellos, de acuerdo a cierto
criterio. Este problema es de gran inter�s tanto desde un punto de vista
algor�tmico como te�rico, adem�s de las importantes aplicaciones que tiene.
El inter�s y la dificultad de este problema tienen ra�z en la naturaleza
combinatoria del mismo: el costo de buscar entre todas las permutaciones
posibles crece exponencialmente con el n�mero de nodos, y por lo tanto se
vuelve r�pidamente intratable, incluso para grafos chicos.*

*La pregunta principal que atacaremos en esta charla es la siguiente:
�cu�ndo el problema de graph matching y su relajaci�n convexa tienen la
misma soluci�n? *

*Primero damos un enfoque probabil�stico mostrando que, asintoticamente, la
relajaci�n convexa m�s com�n falla, mientras que una relajaci�n no convexa
es capaz de resolver el problema con probabilidad uno, siempre y cuando los
grafos originales est�n lo suficientemente correlacionados. Por otro lado,
mencionaremos algunos resultados determin�sticos, que establecien
condiciones sobre los valores y vectores propios de las matrices de
adjacencia de los grafos para garantizar que el problema de graph matching
y su relajaci�n convexa tengan la misma soluci�n.*
------------ pr�xima parte ------------
Se ha borrado un adjunto en formato HTML...
URL: <http://www.cmat.edu.uy/pipermail/seminario-probabilidad-estadistica/attachments/20150909/e19b877e/attachment.html>