Abstract
We propose a dual decomposition and linear program
relaxation of the NP-hard minimum cost multicut problem.
Unlike other polyhedral relaxations of the multicut polytope,
it is amenable to efficient optimization by message passing. Like other polyhedral relaxations, it can be tightened
efficiently by cutting planes. We define an algorithm that
alternates between message passing and efficient separation
of cycle- and odd-wheel inequalities. This algorithm is more
efficient than state-of-the-art algorithms based on linear programming, including algorithms written in the framework
of leading commercial software, as we show in experiments
with large instances of the problem from applications in computer vision, biomedical image analysis and data mining