A message-passing algorithm with damping

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.