Analysis of the Min-Sum Algorithm for Packing and Covering Problems via Linear Programming
Analysis of the Min-Sum Algorithm for Packing and Covering Problems via Linear Programming
Message-passing algorithms based on belief-propagation (BP) are successfully used in many applications, including decoding error correcting codes and solving constraint satisfaction and inference problems. The BP-based algorithms operate over graph representations, called factor graphs, that are used to model the input. Although in many cases, the BP-based algorithms exhibit impressive …