Lifted multicuts on paths: combinatorial optimization and polyhedral geometry
Date
Tuesday, September 11, 2018 16:00 - 18:00
Speaker
Dominik Schröder (IST Austria)
Location
Big Seminar room Ground floor / Office Bldg West (I21.EG.101)
Series
Seminar/Talk
Tags
Mathematics and CS Seminar, mathematical_seminar_ics
Host
Laszlo Erdös
Contact
In this talk we define the concept of lifted multicuts and study polyhedral techniques for their combinatorial optimisation. While the problem is NP-hard for most graphs (including trees), we present results on the facet-defining inequalities for the case of paths. Potential applications include time series segmentation, e.g. word separation in speech recordings.