N&O seminar: Jan-Hendrik Lange (Max-Planck-Institut für Informatik)

Everyone is welcome to attend the N&O lecture of Jan-Hendrik Lange, with the title 'Combinatorial persistency criteria for multicut'.
  • What Networks & Optimization English Seminars
  • When 23-01-2019 from 14:00 to 15:00 (Europe/Amsterdam / UTC100)
  • Where CWI, Lecture room L016
  • Web Visit external website
  • Add event to calendar iCal

 

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.