In the last few years, great interest has been attracted by the relationship between certain approximate free energy functionals (Bethe free energies), developed in the framework of equilibrium statistical mechanics, and Belief Propagation (BP), which is, a class of approximate algorithms for statistical inference and combinatorial optimization, developed independently in the computer science community. Such a relationship has opened new interesting fields of interdisciplinary application of statistical mechanics.
In this work, we consider the application of a BP algorithm to the problem of optimal scheduling for so-called multicast packets in the switching devices of a computer network. Multicast packets differ from ordinary (unicast) packets in that they may have an arbitrary number of destinations. The complexity of the corresponding optimization problem changes from polynomial to NP hard. Belief propagation turns out to provide a good heuristic method for practically solving this problem.