Shengxian Zhao

Box Facets and Cut Facets of Lifted Multicut Polytopes

The lifted multicut problem has diverse applications in the field of computer vision. Exact algorithms based on linear programming require an understanding of lifted multicut polytopes. Despite recent progress, two fundamental questions about these polytopes have remained open: Which lower box inequ…