BriefGPT.xyz
Feb, 2024
抬升多切割凸多面体的切割平面和立方体平面
Cut Facets and Cube Facets of Lifted Multicut Polytopes
HTML
PDF
Lucas Fabian Naumann, Jannik Irmai, Shengxian Zhao, Bjoern Andres
TL;DR
对于提升多割问题的规范化面，本文回答了两个基本问题：哪些下界立方不等式定义了面，哪些割不等式定义了面。并且我们证明了对于割不等式的面定义性判定是NP难的。
Abstract
The
lifted multicut problem
has diverse applications in the field of computer vision. Exact algorithms based on
linear programming
require an understanding of
→