We propose a modified belief propagation algorithm, with overrelaxed dynamics. Such an algorithm turns out to be generally more stable and faster than ordinary belief propagation. We characterize the performance of the algorithm, employed as a tool for combinatorial optimization, on the random satisfiability problem. Moreover, we trace a connection with a recently proposed double-loop algorithm for minimizing Bethe and Kikuchi free energies.
A message-passing algorithm with damping
Pretti M
2005
Abstract
We propose a modified belief propagation algorithm, with overrelaxed dynamics. Such an algorithm turns out to be generally more stable and faster than ordinary belief propagation. We characterize the performance of the algorithm, employed as a tool for combinatorial optimization, on the random satisfiability problem. Moreover, we trace a connection with a recently proposed double-loop algorithm for minimizing Bethe and Kikuchi free energies.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
