On Binary Max-Sum and Tractable HOPs
Marc Pujol-González, Jesús Cerquides, Gonzalo Escalada-Imaz, Pedro Meseguer, Juan A. Rodríguez-Aguilar · DIGITAL.CSIC (Spanish National Research Council (CSIC)) · 2013
The Max-Sum message-passing algorithm has been used to approximately solve several unconstrained optimization problems, specially in the distributed context. In general, the complexity of computing messages is exponential. However, if the problem is modeled using the so called Tractable HOPs (THOPs), binary MaxSum's messages can be computed in polynomial time. In this paper we review existing THOPs, and present new ones, aiming at providing an updated view of efficient message computation.