Title | On Binary Max-Sum and Tractable HOPs |

Publication Type | Conference Paper |

Year of Publication | 2013 |

Authors | Pujol-Gonzalez M [1], Cerquides J [2], Escalada-Imaz G [3], Meseguer P [4], Rodríguez-Aguilar JA [5] |

Editor | Lorini E [6] |

Conference Name | 11th European Workshop on Multi-agent Systems (EUMAS 2013) |

Volume | 1113 |

Conference Location | Toulouse, France |

Date Published | 12/12/2013 |

Abstract | 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. |