The Assignment Problem is a polynomial problem, restated graphically as optimal weighted dimer covering on a bipartite graph. The Hungarian Algorithm (Kuhn, 1955) is a performing solution tool, which involves the construction of graphical structures. We show how the RS Cavity Method (a.k.a. Belief Propagation) allows to devise a new exact algorithm, which is elementary, purely algebraic and interruptible.
This construction is intended also as a playground to understand aspects of the more subtle 1RSB Cavity Method (a.k.a. Survey Propagation) in hard problems, and its approximations due to feedback loops. Indeed, a crucial lemma in proving that Cavity solves the Assignment Problem (Bayati-Shah-Sharma, 2005) relies on the comprehension of the virtuous role of loops within the algorithm.