Linear Programming Relaxations and Belief Propagation -- An Empirical Study

The problem of finding the most probable (MAP) configuration in graphical models comes up in a wide range of applications. In a general graphical model this problem is NP hard, but various approxim...