Séminaire MODAL'X : Nathanaël Enriquez (LMO)

Résumé : On commencera par considérer le problème d'optimisation (déterministe !) très simple suivant. On considère un graphe rectiligne constitué de n arêtes ayant chacune un poids. On veut sélectionner dans ce graphe une famille d'arêtes n'ayant entre elles aucun sommet en commun et dont la somme des poids est maximale. La méthode de "belief propagation" apporte une solution à ce problème déterministe. L'asymptotique de cette solution s'étudie de manière très simple quand les poids sont iid et que n tend vers l'infini.Bien malheureusement (mais assez logiquement !), la méthode s'écroule lorsque le graphe sous-jacent contient des boucles... Peut-on malgré tout répondre aux questions asymptotiques du dessus lorsque l'on a affaire à des graphes dont la limite locale est arborescente ?
Travaux en collaboration avec Mike Liu, Laurent Ménard et Vianney Perchet.