Everyone is welcome to attend this N&O lecture:
Speaker: Jan-Hendrik Lange (Max-Planck-Institut für Informatik)
Title: Combinatorial persistency criteria for multicut
The multicut problem (aka weighted correlation clustering) is a combinatorial optimization problem used to model, for instance, 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.
