Problèmes d'optimisation sur des graphes aléatoires
Nous commencerons par une revue de quelques problèmes célèbres d’optimisation sur des graphes aléatoires : voyageur de commerce (Krauth-Mézard, Aldous), problème d’appariement (Mézard-Parisi, Aldous)… Leur solution n’est souvent pas simple et la réponse peut paraître, de prime abord, contre-intuitive.




