TitleOn Binary Max-Sum and Tractable HOPs
Publication TypeConference Paper
Year of Publication2013
AuthorsPujol-Gonzalez M, Cerquides J, Escalada-Imaz G, Meseguer P, Rodríguez-Aguilar JA
EditorLorini E
Conference Name11th European Workshop on Multi-agent Systems (EUMAS 2013)
Conference LocationToulouse, France
Date Published12/12/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.