---
res:
bibo_abstract:
- Consider a convex relaxation f̂ of a pseudo-Boolean function f. We say that the
relaxation is totally half-integral if f̂(x) is a polyhedral function with half-integral
extreme points x, and this property is preserved after adding an arbitrary combination
of constraints of the form x i=x j, x i=1-x j, and x i=γ where γ∈{0,1,1/2} is
a constant. A well-known example is the roof duality relaxation for quadratic
pseudo-Boolean functions f. 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 relaxations f̂ by establishing a one-to-one correspondence
with 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. On the conceptual level,
our results show that bisubmodular functions provide a natural generalization
of the roof duality approach to higher-order terms. This can be viewed as a non-submodular
analogue of the fact that submodular functions generalize the s-t minimum cut
problem with non-negative weights to higher-order terms.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Vladimir
foaf_name: Kolmogorov, Vladimir
foaf_surname: Kolmogorov
foaf_workInfoHomepage: http://www.librecat.org/personId=3D50B0BA-F248-11E8-B48F-1D18A9856A87
bibo_doi: 10.1016/j.dam.2011.10.026
bibo_issue: 4-5
bibo_volume: 160
dct_date: 2012^xs_gYear
dct_language: eng
dct_publisher: Elsevier@
dct_title: Generalized roof duality and bisubmodular functions@
...