A Message Passing Algorithm for the Minimum Cost Multicut Problem
This addresses efficiency challenges in solving multicut problems for applications like computer vision and data mining, though it is incremental as it builds on existing polyhedral relaxations.
The authors tackled the NP-hard minimum cost multicut problem by proposing a dual decomposition and linear program relaxation amenable to message passing, showing it is more efficient than state-of-the-art linear programming algorithms in experiments with large instances from computer vision, biomedical image analysis, and data mining.
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 elaxations, 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.