The multicut problem (aka weighted correlation clustering) is a combinatorial
optimization problem used to model 2D- and 3D-segmentation tasks in computer
vision. Despite its NP-hardness in the worst case, practical instances often
exhibit substantial structural simplicity. This is indicated by high quality
heuristic solutions and LP relaxations that are fairly tight. In this talk, we
present methods that exploit these observations for the purpose of optimization.
We introduce combinatorial persistency criteria to efficiently compute partial
optimality guarantees on practical instances. Our techniques range from
elementary criteria that can be checked enumeratively in a fast preprocessing
step to more expensive criteria that incorporate both fast primal and dual
heuristics. We demonstrate the effectiveness of our methods on common
benchmarks as well as large biomedical 3D-segmentation instances.