Generalized roof duality and bisubmodular functions
Generalized roof duality and bisubmodular functions
复制标题
广义屋顶对偶性和双子模函数
DOI：
10.1016/j.dam.2011.10.026
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
V. Kolmogorov
中科院分区：
文献类型：
--
作者：
V. Kolmogorov
考虑伪布尔函数的凸松弛。如果f(Bx)$是具有半积分极值点的多面体函数，则称松弛是{em完全半积分}，并且在添加任意形式的约束组合后保持这一性质，其中是一个常数。一个著名的例子是二次伪布尔函数的{em屋脊对偶}松弛。我们认为，完全半积分是将屋顶对偶推广到任意伪布尔函数的一个自然要求。我们的贡献如下。首先，我们通过建立与{em双子模函数}的一一对应关系，给出了完全半积分松弛的完全刻画。其次，我们给出了双子模函数的一个新刻画。最后，我们证明了一般完全半积分松弛与基于屋顶对偶的松弛之间的一些关系。
Consider a convex relaxationof a pseudo-boolean function. We say that the relaxation is {\em totally half-integral} if $\hat f (\bx) $ is a polyhedral function with half-integral extreme points $\bx $, and this property is preserved after adding an arbitrary combination of constraints of the form,, andwhereis a constant. A well-known example is the {\em roof duality} relaxation for quadratic pseudo-boolean functions. We argue that total half-integrality is a natural requirement for generalizations of roof duality to arbitrary pseudo-boolean functions. Our contributions are as follows. First, we provide a complete characterization of totally half-integral relaxationsby establishing a one-to-one correspondence with {\em bisubmodular functions}. Second, we give a new characterization of bisubmodular functions. Finally, we show some relationships between general totally half-integral relaxations and relaxations based on the roof duality.