Statusvortrag im Promotionsver­fahren von Herrn Shengxian Zhao

Abstract: 
Image segmentation seeks to partition a digital image into perceptually meaningful subsets of pixels. By representing the image as a graph, the problem of finding an optimal segmentation can be reformulated as a combinatorial optimization problem. We investigate two different but related approaches from a polyhedral point of view: The lifted multicut problem generalizes the well-known multicut problem by taking into account long-range interactions between pixels while preserving feasible solutions. Although this problem has been studied theoretically and proven useful in applications, important questions regarding the inequalities that appear in an integer linear program formulation of the problem have remained unanswered. We settle these questions by establishing a complete and efficiently decidable characterization of facet-defining lower box inequalities and showing that deciding whether a cut inequality is facet-defining is NP-hard [1]. This hardness motivates the study of the multi-separator problem [2] where connectedness is specified by nodes instead of edges. We initiate the polyhedral study of this new problem and give complete and efficiently decidable characterizations of all facet-defining canonical inequalities, including the counterparts of cut inequalities. This adds to practical advantages [2] of multi-separators over multicuts a geometric property. 

References: 
[1] Naumann L. F., Irmai J., Zhao S. and Andres B. Box Facets and Cut Facets of Lifted Multicut Polytopes. International Conference on Machine Learning (ICML) 2024 
[2] Irmai J., Zhao S., Schöne M., Presberger J. and Andres B. A Graph Multi-separator Problem for Image Segmentation. Journal of Mathematical Imaging and Vision 66(5):839-872, 2024