[Todos CMAT] 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/todos/attachments/20150909/e19b877e/attachment.html>