Sur l'exactitude de la méthode de cavité pour les b-appariements pondérés sur des graphes arbitraires et sa relation avec les programmes linéaires

Nous considérons le problème général de trouver le b-appariement de poids minimum sur des graphes arbitraires. Nous prouvons que, chaque fois que la relaxation de programmation linéaire du problème n'a pas de solutions fractionnaires, les équations de cavité ou de propagation des croyances convergent vers la bonne solution, tant pour la mise à jour synchrone qu'asynchrone.